메뉴 건너뛰기

문제

00b07 바이러스 감염 2  

시간메모리제출 올바른 답 비율
1초64MB
1265
593
46.9%


나의 횟수나의 최근 판정시도 성공 비율
211183
86.7%
바이러스 감염 

1번부터 번호가 부여된 N개의 컴퓨터가 인터넷 선으로 서로 연결되어 있다. 이때, 한 컴퓨터가 바이러스에 감염이 되면, 1분이 경과된 후에는 그 컴퓨터와 인터넷 선으로 직접 연결된 컴퓨터들도 감염된다. 이때, 1번 컴퓨터가 최초로 바이러스에 감염되고 나서, N개의 컴퓨터들이 모두 바이러스에 감염되려면 몇 분이 소요되는지를 구하는 프로그램을 작성하시오.

예를 들어, 3개의 컴퓨터들이 인터넷 선으로 <그림 1>과 같이 서로 연결되어 있는 경우 1번 컴퓨터가 바이러스에 감염되고 2분이 지나면 모든 컴퓨터들이 감염되게 된다.


<그림1>

3개의 컴퓨터들이 인터넷 선으로 <그림 2>와 같이 서로 연결되어 있는 경우 1번 컴퓨터가 바이러스에 감염되고 1분이 지나면 모든 컴퓨터들이 감염되게 된다.


<그림2>

6개의 컴퓨터들이 인터넷 선으로 <그림 3>과 같이 서로 연결되어 있는 경우 1번 컴퓨터가 바이러스에 감염되고 2분이 지나면 모든 컴퓨터들이 감염되게 된다.


<그림3>

입력

첫째 줄에는 컴퓨터의 수 N이 주어진다. N은 1 이상 100 이하이고 각 컴퓨터에는 1번부터 차례대로 번호가 매겨진다.

둘째 줄에는 인터넷 선으로 직접 연결되어 있는 컴퓨터의 쌍의 개수가 주어진다. 이어서 그 수 만큼 한 줄에 한 쌍씩 인터넷 선으로 직접 연결된 컴퓨터의 번호 쌍이 주어진다. (인터넷 선으로 직접 연결된 두 컴퓨터의 번호가 빈칸 1개를 사이에 두고 한 쌍으로 주어진다.)

출력

1번 컴퓨터가 바이러스에 감염되었을 때, N개의 컴퓨터가 모두 바이러스에 감염되는 걸리는 소요 시간(분 단위)을 첫째 줄에 출력한다.

예시
1입력
3
2
1 2
2 3
출력
2
2입력
3
2
1 2
1 3
출력
1
3입력
6
5
1 2
1 4
2 3
4 5
4 6
출력
2
위로