A. Rainbow
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Let $$$T = (V, E)$$$ be a tree with $$$n$$$ vertices and $$$n-1$$$ edges. Each edge of the tree can be assigned a colour from $$$\{0, 1, \dots, K-1\}$$$.

A simple path in a tree is called a $$$K$$$-rainbow path if all edges along the path of length $$$K$$$ have distinct colours. An edge is said to be $$$K$$$-rainbow-valid if it lies on at least one $$$K$$$-rainbow path. A tree is called a $$$K$$$-tree if every edge in the tree is $$$K$$$-rainbow-valid.

Your task is to assign colours to the edges of a given tree to form a K-tree with the largest possible $$$K$$$. For each edge $$$e$$$, you must report its assigned colour $$$c(e) \in \{0, 1, \dots, K-1\}$$$ and the endpoints of a K-rainbow path that contains $$$e$$$.

All indices are zero-based. If multiple valid colourings or paths exist, any may be output.

Input

The first line contains a single integer $$$ n $$$ $$$(2 \leq n \leq 10^5)$$$. In the next $$$n - 1$$$ lines you are given the edges of the tree. In each of these lines you are given $$$u$$$ and $$$v$$$ $$$(0 \leq u, v \leq n - 1)$$$ describing an edge between nodes $$$u$$$ and $$$v$$$.

Output

Your output must consist of $$$n$$$ lines.

In the first line print the maximum possible $$$K$$$.

In the next $$$n - 1$$$ lines, each line should contain three integers: $$$c$$$, $$$u$$$ and $$$v$$$, where $$$0 \leq c \leq K - 1$$$ and $$$0 \leq u, v \leq n - 1$$$. These integers specify the colour $$$c$$$ of an edge and the path between $$$u$$$ and $$$v$$$. This path includes the edge $$$e$$$ and is a K-rainbow. The order of $$$u$$$ and $$$v$$$ does not matter.

Edges must be printed in the order they were given in the input.

Examples
Input
3
0 1
2 1
Output
2
1 2 0
0 0 2
Input
6
0 4
2 3
5 0
2 1
2 0
Output
3
2 3 4
0 4 3
2 3 5
0 4 1
1 3 4
Input
16
2 3
2 4
4 5
5 0
1 5
6 7
4 6
8 7
3 9
4 10
7 11
8 12
10 13
14 12
15 9
Output
7
6 8 15
5 8 15
5 14 0
6 14 0
6 14 1
3 3 14
4 8 15
2 3 14
0 8 15
5 14 13
2 15 11
1 3 14
6 14 13
0 3 14
1 8 15
Note

This is the second sample test. We have a tree with 6 nodes. Colours are written on the edges. Maximum possible K is 3 and for every edge $$$e$$$ there exists a path that includes $$$e$$$ and is a 3-rainbow.

Edge $$$e_1 = \{0, 4\}$$$ has colour 2, the path between 3 and 4 includes $$$e_1$$$ and is a 3-rainbow.

Edge $$$e_2 = \{2, 3\}$$$ has colour 0, the path between 4 and 3 includes $$$e_2$$$ and is a 3-rainbow.

Edge $$$e_3 = \{5, 0\}$$$ has colour 2, the path between 3 and 5 includes $$$e_3$$$ and is a 3-rainbow.

Edge $$$e_4 = \{2, 1\}$$$ has colour 0, the path between 4 and 1 includes $$$e_4$$$ and is a 3-rainbow.

Edge $$$e_5 = \{2, 0\}$$$ has colour 1, the path between 3 and 4 includes $$$e_5$$$ and is a 3-rainbow.