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