Network Topology

题意翻译

# 题目描述 Polycarpus在一家公司担任系统管理员，该公司的计算机网络是由n台计算机组成，其中由一些计算机通过电缆连接了起来 Polycarpus想要找出网络的拓扑结构，拓扑结构是描述网络中计算机的位置和连接的一种方式。 Polycarpus知道三种拓扑结构：链形、环形和星形。 链形结构的特点是连接所有计算机的电缆可以构成一条链 环形结构的特点是每条电缆仅将计算机与另外两个计算机连接 星形结构的特点是除中央计算机的每个计算机都连接到一个中央计算机 以下三幅图分别为一种链形结构、环形结构、星形结构  现在给你一个连通的无向图，表示Polycarpus公司的计算机网络。请你帮Polycarpus判断给出的网络的拓扑类型。 # 输入格式 第一行包含两个整数n和m $4 ≤ n ≤ 105; 3 ≤ m ≤ 105)，分别表示图的节点数和边数。接下来m行给出图的边的描述。第i行包含两个整数$x_i$, $y_i$(1 ≤ $x_i$, $y_i$ ≤ n)，表示被第i条边连着的两个节点的编号。 输入保证给出的图是连通的，并且两个节点之间最多只有一条边，也不会有边连接一个节点和它本身。 # 输出格式 输出图的网络拓扑名称。如果是链形结构，输出"bus topology"；如果是环形结构，输出"ring topology"；如果是星形结构，输出"star topology"。如果非上述三种类型之一，输出"unknown topology"**任何一种输出都不含双引号**。

题目描述

This problem uses a simplified network topology model, please read the problem statement carefully and use it as a formal document as you develop the solution. Polycarpus continues working as a system administrator in a large corporation. The computer network of this corporation consists of $ n $ computers, some of them are connected by a cable. The computers are indexed by integers from $ 1 $ to $ n $ . It's known that any two computers connected by cable directly or through other computers Polycarpus decided to find out the network's topology. A network topology is the way of describing the network configuration, the scheme that shows the location and the connections of network devices. Polycarpus knows three main network topologies: bus, ring and star. A bus is the topology that represents a shared cable with all computers connected with it. In the ring topology the cable connects each computer only with two other ones. A star is the topology where all computers of a network are connected to the single central node. Let's represent each of these network topologies as a connected non-directed graph. A bus is a connected graph that is the only path, that is, the graph where all nodes are connected with two other ones except for some two nodes that are the beginning and the end of the path. A ring is a connected graph, where all nodes are connected with two other ones. A star is a connected graph, where a single central node is singled out and connected with all other nodes. For clarifications, see the picture. (1) — bus, (2) — ring, (3) — starYou've got a connected non-directed graph that characterizes the computer network in Polycarpus' corporation. Help him find out, which topology type the given network is. If that is impossible to do, say that the network's topology is unknown.

输入输出格式

输入格式

The first line contains two space-separated integers $ n $ and $ m $ $ (4<=n<=10^{5}; 3<=m<=10^{5}) $ — the number of nodes and edges in the graph, correspondingly. Next $ m $ lines contain the description of the graph's edges. The $ i $ -th line contains a space-separated pair of integers $ x_{i} $ , $ y_{i} $ $ (1<=x_{i},y_{i}<=n) $ — the numbers of nodes that are connected by the $ i $ -the edge. It is guaranteed that the given graph is connected. There is at most one edge between any two nodes. No edge connects a node with itself.

输出格式

In a single line print the network topology name of the given graph. If the answer is the bus, print "bus topology" (without the quotes), if the answer is the ring, print "ring topology" (without the quotes), if the answer is the star, print "star topology" (without the quotes). If no answer fits, print "unknown topology" (without the quotes).

输入输出样例

输入样例 #1

4 3
1 2
2 3
3 4

输出样例 #1

bus topology

输入样例 #2

4 4
1 2
2 3
3 4
4 1

输出样例 #2

ring topology

输入样例 #3

4 3
1 2
1 3
1 4

输出样例 #3

star topology

输入样例 #4

4 4
1 2
2 3
3 1
1 4

输出样例 #4

unknown topology