케빈 베이컨의 6단계 법칙

케빈 베이컨 게임에서는 두 사람이 서로 아는 사이로 이어지는 최소 단계를 계산한다. 한 사람의 케빈 베이컨 수는 그 사람이 다른 모든 사람과 연결되는 최소 단계 수의 합이다.

N명의 사람과 M개의 친구 관계가 주어진다. 모든 사람은 친구 관계를 따라 서로 도달할 수 있다. 각 사람의 케빈 베이컨 수를 계산했을 때, 값이 가장 작은 사람의 번호를 출력하는 프로그램을 작성하시오. 값이 같은 사람이 여러 명이면 번호가 가장 작은 사람을 선택한다.

첫째 줄에 사람의 수 N (2 <= N <= 100)과 친구 관계의 수 M (1 <= M <= 5,000)이 주어진다. 다음 M개의 줄에는 친구 관계 A B가 주어진다. A와 B는 서로 친구이며, 친구 관계는 양방향이다.

A와 B가 같은 경우는 없지만 같은 친구 관계가 중복되어 주어질 수 있다. 친구가 한 명도 없는 사람은 없고, 모든 사람은 친구 관계를 따라 연결되어 있다. 사람 번호는 1부터 N까지이다.

첫째 줄에 케빈 베이컨 수가 가장 작은 사람의 번호를 출력한다. 여러 사람이 같은 최솟값을 가지면 가장 작은 번호를 출력한다.