[Login|Register]
Problems

Status

Rank

Problem 1210
招商银行网络系统
Time Limit: 1000ms
Memory Limit: 65536kb
Description
虽然招商银行的网络安全已经做得非常完善,但是天有不测风云,招商银行内部网络系统的一台服务器意外感染了一种新型病毒。为了避免更大的损失,管理员必须采取紧急措施遏制病毒的蔓延。
招商银行内部网络系统共有n台服务器,这n台服务器使用m条电缆互相连接。为了描述方便,我们给服务器编号1到n。初始时,1号服务器感染了病毒。每隔一分钟,病毒便会从已感染病毒的服务器扩散到所有与之直接相连的服务器上。
招商银行的网络系统设计得非常坚固,即使要切断电缆也非常困难。管理员只能在初始时切断一根电缆。为了让整个网络系统尽可能晚地全部被病毒感染,他应该切断哪根电缆?
Input
输入包含多组数据。
每组数据的第一行是两个整数n和m (2≤n≤200, 1≤m≤n*(n-1)/2),其含义如上面所描述。
接下来m行每行两个整数a, b (1≤a, b≤n),表示服务器a和服务器b有电缆直接连接。任意两台服务器间至多有一根电缆相连。
输入数据以n=m=0结束。
Output
对每组数据输出最晚多少分钟之后整个网络系统被感染。如果切断某根电缆后病毒永远不会传播到某些服务器,那么输出”Great”。
Sample Input
4 5
1 2
2 3
3 4
4 1
1 3
4 4
1 2
2 3
3 4
1 3
0 0
Sample Output
2
Great
University of Science and Technology of China
Online Judge for ACM/ICPC
Processed in 1.1ms with 1 query(s).