문제

작은 세상 네트워크(Small World Network)란 Milgram 교수가 1967년에 처음으로 밝혀낸 이론이다.

간단히 설명하자면 전체 네트워크가 거대하더라도 전체가 서로 가깝게 연결될 수 있다는 이론이다.

해당 이론에서 Milgram 교수는 지구에 있는 모든 사람들이 최대 6단계로 연결될 수 있다고 주장하였다.

예를 들어 이 문제를 만든 김 모 씨(23)와 이지은님(27)이 서로 생판 모르는 관계라도 최대 6단계만 거치면 서로 연결이 되어있다는 것이다.

위의 그림에서 정점은 사람, 간선은 친구 관계라 할 때 왼쪽 그래프의 모든 정점들은 서로 최소 6단계 이하로 연결되어 있으므로 작은 세상 네트워크를 만족한다. 그러나 오른쪽 그래프의 초록색 정점끼리는 최소 7단계를 거쳐서 연결되어 있으므로 작은 세상 네트워크를 만족하지 않는다.

이 이론에 대해 의구심이 생긴 김 모 씨는 정말 최대 6단계만 거치면 지구상의 모든 사람들이 서로 연결이 될 수 있는지 확인하고 싶었다.

김 모 씨를 위해 지구상의 모든 사람들의 친구 관계가 주어졌을 때 작은 세상 네트워크가 실제로 만족하는지 확인하는 프로그램을 만들어보자.

# 18243
import sys
input = lambda : sys.stdin.readline().strip()
INF = int(1e9)

n, k = map(int, input().split())
graph = [[INF] * (n+1) for _ in range(n+1)]

for _ in range(k):
    a, b = map(int, input().split())
    graph[a][b] = 1
    graph[b][a] = 1
    
for i in range(1, n+1):
    graph[i][i] = 0
    
for m in range(1, n+1):
    for a in range(1, n+1):
        for b in range(1, n+1):
            graph[a][b] = min(graph[a][b], graph[a][m] + graph[m][b])
            
for g in graph[1:]:
    if max(g[1:]) > 6:
        print("Big World!")
        exit(0)
print("Small World!")

백준 18243 Small World Network