이번 문제는 플로이드-와샬 알고리즘을 통해 쉽게 해결할 수 있었다. 우선 n+1크기의 2차원 리스트를 선언해주고, 친구 관계를 입력받을 때마다 양방향으로 2차원 리스트를 1로 갱신해준다. 그리고 플로이드-와샬 알고리즘을 통해 건너서 친구가 있는 경우를 찾아 값을 채워준다. 완성된 2차원 리스트를 순회하며 각 회원의 점수를 리스트로 정리하고, 그 중 최솟값을 가지는 회원들을 따로 정답 리스트에 저장하였다.

Code

n = int(input())
member = [[1e9 for _ in range(n+1)] for _ in range(n+1)]
while True:
    a, b = map(int, input().split())
    if a == -1 and b == -1:
        break
    member[a][b] = 1
    member[b][a] = 1
for k in range(1, n+1):
    for i in range(1, n+1):
        for j in range(1, n+1):
            if i == j:
                member[i][j] = 0
            else:
                member[i][j] = min(member[i][j], member[i][k] + member[k][j])
result = [0]
for i in range(1, n+1):
    result.append(max(member[i][1:]))
mn = min(result[1:])
answer = []
for i in range(1, n+1):
    if result[i] == mn:
        answer.append(i)
print(mn, len(answer))
print(*answer)