Description

There are $N$ houses in a village, connected by $N - 1$ roads, and each road has length $1$.

At the beginning, the $i$-th villager lives in house $i$. The houses are numbered from $1$ to $N$.

One day, the villagers suddenly decide to move to other houses. They want that after moving, no villager lives in the house they originally lived in.

Find the minimum and maximum possible total distance, summed over all villagers, between their old and new houses.

Input Format

The first line contains an integer $N$, the number of houses.
The next $N - 1$ lines each contain two integers $a, b$, representing a road connecting house $a$ and house $b$.

Output Format

The first line contains two integers: the minimum total distance and the maximum total distance between the villagers’ old and new houses.
The second line contains $N$ integers, giving one plan that achieves the minimum total distance. The $i$-th integer $v_i$ means that villager $i$ moves from house $i$ to house $v_i$.
The third line contains $N$ integers, giving one plan that achieves the maximum total distance. The output format is the same as the previous line.
You must ensure that $v_i \ne i$.
If there are multiple solutions, output any valid one.

4
1 2
2 3
3 4

4 8
2 1 4 3
4 3 2 1

7
4 2
5 7
3 4
6 3
1 3
4 5

8 18
6 4 1 2 7 3 5
7 3 4 1 2 5 6

Hint

Scoring

This problem consists of two tasks:

• Compute the minimum total distance and output one corresponding valid plan.
• Compute the maximum total distance and output one corresponding valid plan.

Each task is worth $50\%$ of the score for a test point.

Your score for a subtask equals the lowest score among all test points in that subtask.

Note that even if you cannot solve one of the subtasks, you still must follow the required output format. Otherwise, the checker cannot score your submission correctly.

Constraints

This problem uses bundled testdata.

• Subtask 1 (12 pts): $N \le 10$.
• Subtask 2 (38 pts): $N \le 1000$.
• Subtask 3 (50 pts): no additional constraints.

For $100\%$ of the testdata, $1 \le N \le 10^5$, $1 \le a, b \le N$.

This problem uses a Special Judge.

Translated by ChatGPT 5