주어진 트리에 최대한 많은 간선을 추가하여 결과 그래프가 선인장 그래프(cactus graph)가 되도록 하시오.

선인장 그래프는 모든 간선이 최대 하나의 단순 사이클에 포함되는 그래프입니다. 이 그래프는 자기 루프(self-loop)나 다중 간선(parallel edge)을 포함할 수 없습니다.

입력

첫 번째 줄에는 트리의 크기인 정수 $N$이 주어집니다 ($1 \le N \le 200\,000$).

다음 $N - 1$개의 줄에는 각각 두 정수 $u$와 $v$가 주어지며 ($1 \le u, v \le N, u \neq v$), 이는 노드 $u$와 $v$ 사이에 간선이 있음을 나타냅니다. 주어진 그래프는 트리임이 보장됩니다.

출력

첫 번째 줄에 그래프에 추가할 수 있는 최대 간선의 개수 $K$를 출력하십시오. 이어지는 $K$개의 줄에는 각각 두 정수 $a$와 $b$를 출력하여 ($1 \le a, b \le N, a \neq b$), 노드 $a$와 $b$ 사이에 간선을 추가함을 나타내십시오. 결과 그래프는 선인장 그래프여야 합니다.

최대 $K$를 만족하는 해가 여러 개라면, 그중 아무거나 하나를 출력하십시오.

예제

입력 1

6
6 4
3 1
3 6
4 5
2 3

출력 1

2
2 1
3 5