[1389] 케빈 베이컨의 6단계 법칙

import sys

from collections import deque

input = sys.stdin.readline

# 입력

n, m = map(int, input().split())

# 초기화

friends = [[] for i in range(n+1)]

Min = sys.maxsize

answer = 0

# 관계 입력

for i in range(m):

    a, b =  map(int, input().strip().split())

    # 양방향

    friends[a].append(b)

    friends[b].append(a)

# 정렬

for f in friends:

    f.sort()

def bfs(i,j):

    # i = 나, 0 = 거리    

    q = deque([(i, 0)])

    visited = [False for _ in range(n+1)]

    visited[i] = True

    while q:

        cur, dis= q.popleft()

        # 목적지까지 갈 수 있다면 거리 출력

        if cur == j:

            return dis

        # 내가 아는 친구들만 탐색

        for f in friends[cur]:

            # 아직 안만나본 친구인가?

            if not visited[f]:

                # 만남

                visited[f] = True

                # 새 친구와 거리를 1늘려 큐에 저장

                q.append((f,dis+1))

    # 목적지까지 아는 친구 없으면 0

    return 0

for i in range(1, n+1):

    sum = 0

    # i부터 j까지 반복하기 그걸 sum에다가 더하기 걔를 기준으로 정답 구하기

    if friends[i]:

        for j in range(1, n+1):

            if i == j: continue

            sum += bfs(i,j)

        if Min > sum:

            Min = sum

            answer = i

print(answer)