[KOITP] 상인(Not Solved)

출    처 : http://koitp.org/problem/SDS_PRO_4_8/read/

시간 제한	메모리 제한	제출 횟수	정답 횟수 (비율)	정답자 수
1.0 초	512 MB	1134	131 (12%)	93

문제

사막에 N(1≤N≤100,000)개의 도시가 있고, 각 도시에는 1부터 N까지의 번호가 매겨져 있다. 두 도시를 연결하는 N-1개의 길이 있으며, 임의의 두 도시 사이에는 길들을 따라 이동할 수 있는 경로가 하나만 존재한다. 어떤 사람이 하나의 길을 지나는 데는 정확히 하루가 걸리며, 길 이외의 장소에서는 마실 물을 구할 수 없어 이동할 수 없다.

한 상인이 1번 도시부터 N번 도시까지를 순서대로 방문하며 장사를 하려고 한다. 이 상인이 1번 도시부터 N번 도시까지 순서대로 방문하는데 며칠이 걸리는지를 계산하여 출력하시오.

제한 시간 : 1초

입력

첫 줄에 도시의 수 N(1≤N≤100,000)이 주어진다.

두 번째 줄부터 N번째 줄까지는 각각의 줄에 하나의 길의 정보가 주어진다. 하나의 줄에는 두 개의 서로 다른 1 이상 N 이하의 정수가 주어지며, 이는 이 두 도시를 연결하는 길이 존재한다는 의미이다.

출력

상인이 1번 도시에서 출발하여 2번 도시, ..., N-1번 도시를 순서대로 거쳐 N번 도시에 도착하기까지 며칠이 결리는지를 출력한다.

힌트

입력 예제

5
3 1
2 4
3 5
1 4

출력 예제

10