난쿤이네 도시에는 여러명의 사람들이 있다.

어느날 마을이 모임을 갖는데, 마을에서 N명의 사람이 모임에 참석한다. 이 사람들은 나머지 N-1명 중 원수관계인 사람이 적어도 1명 있다.

원수관계인 사람들은 같은 테이블에 앉을 수 없고, 원수관계인 두 사람의 쌍이 N-1쌍이다.

또한, 원수관계인 두 사람을 이은 선분으로 그래프를 만들면 연결된 트리가 형성된다.

들어오는 사람들의 순서에 따라 필요한 테이블 수가 다르다. 즉, 1,3,5,2,4 순서대로 들어오고 1과 2, 1과 4, 2와 3, 4와 5가 원수관계라면

• 테이블 1에 1이 들어가고
• 테이블 1에 3이 들어가고
• 테이블 1에 5가 들어가고
• 테이블 2에 2가 들어가고
• 테이블 2에 4가 들어가서

반면, 2,5,4,3,1 순서대로 들어온다면

• 테이블 1에 2가 들어가고
• 테이블 1에 5가 들어가고
• 테이블 2에 4가 들어가고
• 테이블 2에 3이 들어가고
• 테이블 3에 1이 들어가서

사람의 수 N, 원수관계인 쌍 N-1개가 주어질 때 필요한 테이블의 수의 최대값을 출력하시오.

입력

• 첫 줄에 사람의 수 N이 주어진다.(1<=N<=300,000)
• 둘째 줄부터 N번째 줄까지 원수 관계인 두 사람 Ai와 Bi가 주어진다.(1<=Ai,Bi<=N)

출력

입출력 예

입력

5 
1 2 
1 4 
2 3 
4 5 

출력

3 

출처:boi 2003
추천:ainta