우정은 BFS처럼, 사랑은 DFS처럼

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

요약

DFS 방문 순서와 BFS 방문 순서의 차이 합을 최대로 하는 트리를 만들어, 최댓값과 그 트리를 출력한다.

난이도: 보통10점 중 7점
유형: 트리, 그리디, BFS, DFS
정답자: 아직 제출이 없습니다

문제

$1$ 부터 $N$ 까지 번호가 매겨진 $N$ 개의 정점으로 이루어진 트리를 구하고자 한다. $1$ 번 정점부터 깊이 우선 탐색과 너비 우선 탐색을 각각 시행했을 때, 다음과 같이 두 수열을 정의한다.

$d\_i=$ 깊이 우선 탐색(DFS)에서 $i$ 번 정점을 방문한 순서
$b\_i=$ 너비 우선 탐색(BFS)에서 $i$ 번 정점을 방문한 순서

두 번의 탐색에서 각 정점을 방문한 순서의 차이를 모두 더했을 때, 이 값을 최대로 하는 트리를 만들고자 한다. 즉, $\sum\_{i=1}^{N}{|d\_i-b\_i|}$ 를 최대로 하는 트리를 만들어 보자. 순회 후보가 여럿인 경우에는 번호가 더 작은 정점을 먼저 방문한다.

입력

정점의 개수 $N$ 이 주어진다. $\left( 3\leq N\leq 200\ 000 \right)$

출력

첫째 줄에 두 순회에서 방문된 순서의 차이를 모두 더했을 때의 최댓값을 출력한다.

둘째 줄부터 $N-1$ 개의 줄에 걸쳐 간선으로 연결된 두 정점의 번호를 공백으로 구분하여 출력한다. 가능한 트리가 여러 가지라면 아무거나 출력한다.

예제2

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