불꽃놀이의 아름다움 2

시간 제한1초메모리 제한1024 MB

요약

정점 N개와 간선 N개로 이루어진 연결 그래프가 주어질 때, 모든 간선의 양 끝 색이 다르도록 하는 최소 색의 개수를 구한다.

난이도: 보통10점 중 6점
유형: 그래프, BFS, DFS, 수학
정답자: 아직 제출이 없습니다

문제

봄 축제 때 정보과학관에서는 아무 행사도 진행되지 않는다는 것에 화가 난 민성이는 정보과학관 입구 앞에서 직접 불꽃놀이 행사를 진행하려고 한다.

민성이는 정보과학관 입구 앞에 $N$ 개의 폭죽과 서로 다른 두 폭죽을 직접 연결하는 도화선 $N$ 개를 설치했다. $N$ 개의 폭죽은 도화선을 통해 모두 직간접적으로 연결되어 있다. 즉, 어떤 한 폭죽에 불을 붙이면 도화선을 따라 모든 $N$ 개의 폭죽에 불이 붙는다.

민성이는 도화선으로 직접 연결된 두 폭죽의 색이 다를 때 불꽃놀이가 아름답다고 생각한다. 하지만 불꽃놀이의 색의 종류를 늘리는 것은 비용이 많이 들기 때문에 최소 개수의 색을 사용하려고 한다. 아름다운 불꽃놀이를 만들기 위해 필요한 색의 개수의 최솟값을 구해보자.

입력

첫째 줄에 폭죽의 개수 $N$ 이 주어진다.

둘째 줄부터 $N$ 개의 줄에 걸쳐, $i$ 번째 도화선이 연결하는 두 폭죽의 번호 $a\_i,b\_i$ 가 공백으로 구분되어 주어진다.

출력

아름다운 불꽃놀이를 만들기 위해 필요한 폭죽 색 종류의 최솟값을 출력한다.

제한

$3\leq N\leq 200\\, 000$
$1\leq a\_i,b\_i\leq N$ ( $1\le i\le N$ )
$N$ 개의 폭죽은 도화선을 통해 모두 서로 연결되어 있다.
도화선은 서로 다른 두 폭죽을 연결하며, 다른 도화선이 같은 쌍을 연결하는 경우는 없다.
입력으로 주어지는 수는 모두 정수이다.

예제2

예제 1
입력
```
5
1 2
2 3
3 4
4 5
5 1
```
예상 출력
```
3
```
예제 2
입력
```
5
1 2
2 3
3 4
4 1
5 1
```
예상 출력
```
2
```