在一个星球上有M个国家和N个城市,一些道路间有道路相连,已知: (1)在任意一个国家里均有至少三座城市。 (2)一个国家里的任意一座城市均与这个国家的至少一半城市通过道路相连。 (3)任意一座城市均与别国有且仅有一座城市通过道路相连。 (4)任两个国家的城市间至多只有两条道路相连。 (5)若两个国家里的城市数目少于2M,则在这两个国家间至少有一条道路相连。 证明:存在一条至少连接M+N/2座城市的环形线路。