Note: This problem differs from cco24p4 only in the scoring.

Ondrej and Edward are spies and they are going to take down the evil organization AQT.

To do so, they will need to infiltrate into the AQT base. The base can be modelled as a tree with ~N = 100~ rooms, labelled from 0 to ~N - 1~. Ondrej and Edward's plan to infiltrate the base is to first get kidnapped and then meet up together before executing their plan. When kidnapped, the two will be placed into different rooms unknown to each other. Once they are placed into the rooms, they will both break free at midnight and try to meet up with each other before executing their plan.

Their plan to meet up is as follows. At every odd minute, Ondrej can choose to stay at his current room or move to an adjacent room. At every even minute, Edward can choose to stay at his current room or move to an adjacent room.

A strategy is defined as the following. Let ~V(A, R, T)~ denote the room agent ~A~ should be at assuming that they were at room ~R~ at midnight and it is currently ~T~ minutes after midnight. The strategy should match the conditions above. The agents are said to meet up at time ~t(o, e)~, which is the first time where ~V(\text{Ondrej}, o, t(o, e)) = V(\text{Edward}, e, t(o, e))~.

Ondrej and Edward want to meet up as fast as possible, relative to the distance between their two starting rooms. The distance ~d(o, e)~ is the minimum number of corridors that must be traversed to reach ~o~ from ~e~. Please help find a strategy that minimizes the maximum ~\frac{t(o,e)}{d(o,e)}~ across all pairs of different rooms ~o~ and ~e~.

Input Specification

The first line of input will contain ~N~ ~(N = 100)~.

The next ~N - 1~ lines will each contain two space-separated integers, denoting the labels of two rooms with a bidirectional corridor between them.

Output Specification

First output a positive number ~T~, the number of entries per starting room. Note that ~T \le 1440~ must be satisfied, otherwise you will be awarded no points.

Then, output Ondrej's strategy, followed by Edward's strategy.

To output an agent's strategy, output ~N~ lines, where the ~n~-th line (starting from 0) represents the agent's path if they start at room ~n~. For each line, output ~T~ spaced integers: The room label that the agent should be in at time 1, 2, . . . , ~T~.

Scoring

If the output is invalid or there exists a test case and a pair of different rooms ~o~ and ~e~ where the agents do not meet at or before time ~T~, then no points will be awarded.

Otherwise, let ~S~ be the maximum among all test cases and pairs of ~o~ and ~e~ ~(o \neq e)~ of the value of ~\frac{t(o,e)}{d(o,e)}~. Let ~S_{opt}~ be the optimal ~S~ known so far. Currently, ~S_{opt} = 12.25~ (please comment below if you believe you've found a more optimal ~S~).

Your score (out of ~100~) will be ~0~ if ~S > 15~ and given by the following expression otherwise. $$\displaystyle \frac{100}{(S_{opt} - 15)^2} (S-15)^2$$

Sample Input 1

5
0 2
3 2
1 4
2 4

Sample Output 1

8
2 2 4 4 1 1 1 1
1 1 1 1 1 1 1 1
3 3 2 2 3 3 2 2
3 3 2 2 0 0 2 2
4 4 4 4 2 2 2 2
0 2 2 3 3 3 3 2
1 4 4 2 2 0 0 0
2 3 3 3 3 3 3 3
3 3 3 3 3 3 3 3
4 1 1 1 1 4 4 4

Explanation for Sample 1

Note that this is an invalid test case as ~N \neq 100~, so it will not appear in the test cases when judging. The output for the test case is valid. Note that this would not score any points because if Ondrej starts at room 1 and Edward starts at room 3, then they will never meet each other.

---