You are given a weighted undirected connected tree that contains n nodes and n - 1 edges.
every edge has a weight and there is exactly one path between every pair of different nodes.
Now you should take each edge independently and do the following :
1.remove the edge from tree (that will divide the tree into two components).
2.reconnect the edge again in which it is still a connected tree (every end of the edge should be connected to a node from a different component).
You should do this so that the longest path in the tree is minimised.
First line contains one integer n (2 ≤ n ≤ 200000)
The next n - 1 lines will contain 3 integers for each,u v w (1 ≤ u, v ≤ n) (1 ≤ w ≤ 109), which means that there is an edge of weight w connecting the nodes u and v.
it is guaranteed that the edges describes one connected tree.
you should print n - 1 lines, the ith line should be the answer for the ith edge.
The sample graph
Solution for the second edge: after removing the second edge, add it to again between Node 2 and Node 3
## Input
First line contains one integer n (2 ≤ n ≤ 200000)The next n - 1 lines will contain 3 integers for each,u v w (1 ≤ u, v ≤ n) (1 ≤ w ≤ 109), which means that there is an edge of weight w connecting the nodes u and v.it is guaranteed that the edges describes one connected tree.
## Output
you should print n - 1 lines, the ith line should be the answer for the ith edge.
[samples]
## Note
The sample graph Solution for the second edge: after removing the second edge, add it to again between Node 2 and Node 3
**Definitions**
Let $ L \in \mathbb{Z} $ be the number of levels.
For each level $ \ell \in \{1, \dots, L\} $, let $ R_\ell = \{(r_{\ell,1}, c_{\ell,1}), (r_{\ell,2}, c_{\ell,2}), (r_{\ell,3}, c_{\ell,3}), (r_{\ell,4}, c_{\ell,4})\} $ be the set of initial positions of four distinct robots on a 12×12 grid, where no cell is blocked.
**Constraints**
1. $ 1 \leq L \leq 1000 $
2. For each $ \ell $, $ 1 \leq r_{\ell,i}, c_{\ell,i} \leq 12 $ for all $ i \in \{1,2,3,4\} $
3. All four robot positions in each level are distinct and lie on non-blocked cells.
**Objective**
Find a sequence of at most 1000 moves (each move being a direction: up, down, left, or right) such that, after applying all moves in order, **all four robots simultaneously end on crossed cells**, under the following movement rules:
- All four robots attempt to move in the same direction simultaneously.
- A robot moves if and only if:
- Its target cell is not blocked, **and**
- Either the target cell is empty or crossed, **or**
- The target cell contains another robot that is itself moving (i.e., that robot’s move is not blocked).
- If a robot is blocked from moving, it remains in place.
- A robot successfully reaches a crossed cell if and only if it ends its movement on a cell marked as crossed.
**Output**
For each level $ \ell $, output a sequence of moves (as strings: "U", "D", "L", "R") of length ≤ 1000 that achieves the objective.