← 返回题目列表

Codeforces · 292/B

B. 网络拓扑

中文机器翻译题面 查看原题

该问题使用简化的网络拓扑模型,请仔细阅读问题陈述并将其用作开发解决方案的正式文档。

Polycarpus 继续在一家大公司担任系统管理员。该公司的计算机网络由n台计算机组成,其中一些计算机通过电缆连接。计算机通过 1 到 n 的整数进行索引。已知任意两台计算机通过电缆直接连接或通过其他计算机连接

Polycarpus 决定找出网络的拓扑结构。网络拓扑是描述网络配置的方式,是显示网络设备位置和连接的方案。

Polycarpus 知道三种主要的网络拓扑:总线、环型和星型。总线是一种拓扑结构,代表所有与其连接的计算机的共享电缆。在环形拓扑中,电缆仅将每台计算机与另外两台计算机连接。星形是网络中所有计算机都连接到单个中央节点的拓扑。

让我们将每个网络拓扑表示为连通的无向图。总线是唯一路径的连通图,即除了作为路径的起点和终点的两个节点之外,所有节点都与另外两个节点连接的图。环是一个连通图,其中所有节点都与另外两个节点连接。星形是一个连通图,其中单个中心节点被挑选出来并与所有其他节点连接。如需说明,请参见图片。

(1) — 总线,(2) — 环形,(3) — 星形

您已获得一个连通的无向图,它描述了 Polycarpus 公司的计算机网络。帮助他找出给定网络的拓扑类型。如果这是不可能的,就说网络的拓扑未知。

输入

第一行包含两个空格分隔的整数 n 和 m (4 ≤ n ≤ 105; 3 ≤ m ≤ 105) — 相应地,图中节点和边的数量。接下来的 m 行包含图边的描述。第 i 行包含一对以空格分隔的整数 xi, yi (1 ≤ xi, yi ≤ n) — 由第 i 条边连接的节点数。

保证给定的图是连通的。任意两个节点之间至多有一条边。没有边将节点与其自身连接起来。

输出

在一行中打印给定图的网络拓扑名称。如果答案是总线,则打印“总线拓扑”(不带引号),如果答案是环型,则打印“环形拓扑”(不带引号),如果答案是星形,则打印“星形拓扑”(不带引号)。如果没有合适的答案,则打印“未知拓扑”(不带引号)。

示例

输入 #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