간선 가중치 할당

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

요약

트리의 간선에 양의 정수 가중치를 배정하여 모든 리프 쌍 사이 경로의 XOR이 0이 되게 합니다. 이때 서로 다른 가중치 개수의 최솟값과 최댓값을 구합니다.

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

문제

정점이 $n$ 개인 가중치 없는 트리가 주어집니다. 각 간선에 양의 가중치를 하나씩 할당해야 합니다. 서로 다른 두 리프 $v_1$ , $v_2$ 마다, 두 정점을 잇는 단순 경로 위 모든 간선 가중치의 XOR 값이 $0$ 이어야 합니다. 가중치는 $10^{10^{10}}$ 처럼 매우 큰 양의 정수여도 됩니다. 주어진 제약에서는 이런 할당이 항상 존재합니다. 할당에 쓰이는 서로 다른 가중치의 개수를 $f$ 라고 합니다. 주어진 트리에서 $f$ 의 최솟값과 최댓값을 구하세요.

입력

첫 줄에 정점의 개수 $n$ ( $3 \le n \le 10^5$ )이 주어집니다. 다음 $n-1$ 개의 줄에는 각각 정수 $a_i$ 와 $b_i$ ( $1 \le a_i < b_i \le n$ )가 주어지며, 이는 $a_i$ 와 $b_i$ 를 잇는 간선이 있다는 뜻입니다. 주어지는 그래프는 $n$ 개의 정점으로 이루어진 트리입니다.

출력

유효한 할당에서 가능한 $f$ 의 최솟값과 최댓값을 공백으로 구분해 두 정수로 출력하세요.

힌트

첫 번째 예시의 그림은 최솟값과 최댓값에 대한 할당을 각각 하나씩 보여 줍니다. 두 값 모두 유효한 할당이 여러 가지 있습니다. 두 번째 예시에서는 유효한 할당의 $f$ 값이 항상 $3$ 입니다. 세 번째 예시의 그림도 최솟값과 최댓값에 대한 할당을 각각 하나씩 보여 줍니다.

예제3

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