30466번 - 우정은 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$개의 줄에 걸쳐 간선으로 연결된 두 정점의 번호를 공백으로 구분하여 출력한다. 가능한 트리가 여러 가지라면 아무거나 출력한다.