Network Topology

题面翻译

题目大意

给你一个 $n(4 \le n \le 10^5)$ 个点，$m (3 \le m \le 10^5)$ 条边的图，询问它是以下的哪种情况：

1. 总线：一个连接的图，所有节点都与另外两个节点连接，除了作为路径起点和终点的节点；
2. 环：一个连接的图，其中所有节点都与另外两个节点连接；
3. 星型：一个连接的图，其中一个单独的中心节点被选出并与所有其他节点连接。

有关详细信息，请参见图片：

输入

第 $1$ 行两个整数 $n,m$

接下来 $m$ 行，对于第 $i+1$ 行，两个整数 $x_i,y_i(1\le x_i,y_i \le 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

样例输入 #1

4 3
1 2
2 3
3 4

样例输出 #1

bus topology

样例 #2

样例输入 #2

4 4
1 2
2 3
3 4
4 1

样例输出 #2

ring topology

样例 #3

样例输入 #3

4 3
1 2
1 3
1 4

样例输出 #3

star topology

样例 #4

样例输入 #4

4 4
1 2
2 3
3 1
1 4

样例输出 #4

unknown topology