The second semester starts at the University of Pavlopolis. After vacation in Vičkopolis Noora needs to return to Pavlopolis and continue her study.
Sometimes (or quite often) there are teachers who do not like you. Incidentally Noora also has one such teacher. His name is Yury Dmitrievich and he teaches graph theory. Yury Dmitrievich doesn't like Noora, so he always gives the girl the most difficult tasks. So it happened this time.
The teacher gives Noora a tree with _n_ vertices. Vertices are numbered with integers from 1 to _n_. The length of all the edges of this tree is 1. Noora chooses a set of simple paths that pairwise don't intersect in edges. However each vertex should belong to at least one of the selected path.
For each of the selected paths, the following is done:
1. We choose **exactly** one edge (_u_, _v_) that belongs to the path.
2. On the selected edge (_u_, _v_) there is a point at some selected distance _x_ from the vertex _u_ and at distance 1 - _x_ from vertex _v_. But the distance _x_ chosen by Noora arbitrarily, i. e. it can be different for different edges.
3. One of the vertices _u_ or _v_ is selected. The point will start moving to the selected vertex.
Let us explain how the point moves by example. Suppose that the path consists of two edges (_v_1, _v_2) and (_v_2, _v_3), the point initially stands on the edge (_v_1, _v_2) and begins its movement to the vertex _v_1. Then the point will reach _v_1, then "turn around", because the end of the path was reached, further it will move in another direction to vertex _v_2, then to vertex _v_3, then "turn around" again, then move to _v_2 and so on. The speed of the points is 1 edge per second. For example, for 0.5 second the point moves to the length of the half of an edge.
A stopwatch is placed at each vertex of the tree. The time that the stopwatches indicate at start time is 0 seconds. Then at the starting moment of time, all points simultaneously start moving from the selected positions to selected directions along the selected paths, and stopwatches are simultaneously started. When one of the points reaches the vertex _v_, the stopwatch at the vertex _v_ is automatically reset, i.e. it starts counting the time from zero.
Denote by _res__v_ the maximal time that the stopwatch at the vertex _v_ will show if the point movement continues infinitely. Noora is asked to select paths and points on them so that _res_1 is as minimal as possible. If there are several solutions to do this, it is necessary to minimize _res_2, then _res_3, _res_4, ..., _res__n_.
Help Noora complete the teacher's task.
For the better understanding of the statement, see the explanation for the example.
## Input
The first line contains single integer _n_ (2 ≤ _n_ ≤ 100) — number of vertices in the given tree.
Each of next _n_ - 1 lines contains two integers _u_ and _v_ (1 ≤ _u_, _v_ ≤ _n_, _u_ ≠ _v_) — vertices connected by an edge.
Guaranteed that input defines a valid tree.
## Output
In the first line print single integer _paths_ — number of paths you want to choose.
In the next _paths_ lines print path's descriptions:
1. Single integer _len_ — number of edges in the current path.
2. _len_ integers — indices of the edges in the path. The edges are numbered from 1 to _n_ - 1 in order they are given in input.
3. Two integers _u_ and _v_ — means that you put point on the edge between vertices _u_ and _v_ (obviously the edge should belong to the path) and a point will start moving to the vertex _v_. Note that **order of printing of the edge's ends is important**. For example if you print "_1 2_" (without quotes), then point will start moving to vertex 2; but if you print "_2 1_" (without quotes), then point will start moving to vertex 1.
4. Single real number _x_ (0 ≤ _x_ ≤ 1) — distance between point and vertex _u_ **(the same vertex that you print first in the third paragraph)**.
[samples]
## Scoring
Judge system will generate array _res_ using the output data provided by the participant. Also system will generate array _resOptimal_ by the jury answer. Your answer will be accepted if only for each _i_ (1 ≤ _i_ ≤ _n_) the following is satisfied: .
## Note
Consider an example.
In starting moment of time points are located as following:
The first path is highlighted in red, the second in blue, green circles represent chosen points, and brown numbers inside vertices — current time at stopwatch. Purple arrows represent direction in which points will move.
In 0.(3) seconds points will be located in following way (before stopwatch reset):
After stopwatch reset:
In 1.0 second after the start of moving:
In 1.(3) seconds after the start of moving (after stopwatch reset):
Finally, in 2 seconds after the start of moving points return to their initial positions.
This process will continue infinitely.
Pavlopolis 大学的第二学期开始了。Noora 在 Vičkopolis 度完假后，需要返回 Pavlopolis 继续她的学业。
有时（或经常）会有一些老师不喜欢你。巧合的是，Noora 也有一位这样的老师。他的名字是 Yury Dmitrievich，教授图论。Yury Dmitrievich 不喜欢 Noora，因此总是给她布置最困难的任务。这次也不例外。
老师给了 Noora 一棵包含 #cf_span[n] 个顶点的树。顶点编号为从 #cf_span[1] 到 #cf_span[n] 的整数，树中所有边的长度均为 #cf_span[1]。Noora 需要选择一组互不相交（在边上无公共边）的简单路径，且每个顶点必须至少属于其中一条选中的路径。
对于每条选中的路径，执行以下操作：
让我们通过一个例子说明点的移动方式。假设路径由两条边 #cf_span[(v1, v2)] 和 #cf_span[(v2, v3)] 组成，点最初位于边 #cf_span[(v1, v2)] 上，并开始朝顶点 #cf_span[v1] 移动。随后，点将到达 #cf_span[v1]，然后“掉头”，因为路径的端点已到达；接着它将朝顶点 #cf_span[v2] 移动，再移动到顶点 #cf_span[v3]，再次“掉头”，然后朝 #cf_span[v2] 移动，依此类推。点的速度为每秒 #cf_span[1] 条边。例如，在 #cf_span[0.5] 秒内，点移动了半条边的长度。
树的每个顶点上都放置了一个秒表。秒表在初始时刻显示的时间为 #cf_span[0] 秒。在起始时刻，所有点同时从选中的位置沿选中的方向开始移动，同时所有秒表也同时启动。当任意一个点到达顶点 #cf_span[v] 时，该顶点上的秒表会自动重置，即从零开始重新计时。
记 #cf_span[resv] 为若点的运动无限持续下去，顶点 #cf_span[v] 上秒表所显示的最大时间。Noora 需要选择路径及路径上的点，使得 #cf_span[res1] 尽可能小。若有多种方案使 #cf_span[res1] 最小，则需进一步最小化 #cf_span[res2]，然后是 #cf_span[res3]、#cf_span[res4, ..., resn]。
请帮助 Noora 完成老师的任务。
为更好理解题意，请参见示例的解释。
第一行包含单个整数 #cf_span[n] (#cf_span[2 ≤ n ≤ 100]) —— 给定树中的顶点数。
接下来的 #cf_span[n - 1] 行，每行包含两个整数 #cf_span[u] 和 #cf_span[v] (#cf_span[1 ≤ u, v ≤ n, u ≠ v]) —— 由一条边连接的两个顶点。
保证输入构成一棵合法的树。
第一行输出单个整数 #cf_span[paths] —— 你选择的路径数量。
接下来的 #cf_span[paths] 行，每行描述一条路径：
裁判系统将根据参赛者提供的输出数据生成数组 #cf_span[res]，同时根据标准答案生成数组 #cf_span[resOptimal]。你的答案将被接受，当且仅当对每个 #cf_span[i] (#cf_span[1 ≤ i ≤ n])，满足：。
考虑一个例子：
在起始时刻，点的位置如下：
第一条路径用红色标出，第二条用蓝色标出，绿色圆圈表示选中的点，顶点内的棕色数字表示秒表当前时间，紫色箭头表示点的移动方向。
在 #cf_span[0.(3)] 秒后，点的位置如下（在秒表重置前）：
秒表重置后：
在起始移动后 #cf_span[1.0] 秒：
在起始移动后 #cf_span[1.(3)] 秒（秒表重置后）：
最终，在起始移动后 #cf_span[2] 秒，点回到初始位置。
该过程将无限循环继续。
## Input
第一行包含单个整数 #cf_span[n] (#cf_span[2 ≤ n ≤ 100]) —— 给定树中的顶点数。接下来的 #cf_span[n - 1] 行，每行包含两个整数 #cf_span[u] 和 #cf_span[v] (#cf_span[1 ≤ u, v ≤ n, u ≠ v]) —— 由一条边连接的两个顶点。保证输入构成一棵合法的树。
## Output
第一行输出单个整数 #cf_span[paths] —— 你选择的路径数量。接下来的 #cf_span[paths] 行，每行描述一条路径：
单个整数 #cf_span[len] —— 当前路径包含的边数。
#cf_span[len] 个整数 —— 路径中边的编号。边按输入顺序编号为从 #cf_span[1] 到 #cf_span[n - 1]。
两个整数 #cf_span[u] 和 #cf_span[v] —— 表示你在顶点 #cf_span[u] 和 #cf_span[v] 之间的边上放置一个点（显然该边必须属于该路径），点将朝顶点 #cf_span[v] 移动。注意：输出边两端的顺序很重要。例如，若你输出 "_1 2_"（不含引号），则点将朝顶点 #cf_span[2] 移动；但若你输出 "_2 1_"（不含引号），则点将朝顶点 #cf_span[1] 移动。
一个实数 #cf_span[x] (#cf_span[0 ≤ x ≤ 1]) —— 点与顶点 #cf_span[u]（即第三段中首先打印的顶点）之间的距离。
[samples]
## Scoring
裁判系统将根据参赛者提供的输出数据生成数组 #cf_span[res]，同时根据标准答案生成数组 #cf_span[resOptimal]。你的答案将被接受，当且仅当对每个 #cf_span[i] (#cf_span[1 ≤ i ≤ n])，满足：。
## Note
考虑一个例子：
在起始时刻，点的位置如下：
第一条路径用红色标出，第二条用蓝色标出，绿色圆圈表示选中的点，顶点内的棕色数字表示秒表当前时间，紫色箭头表示点的移动方向。
在 #cf_span[0.(3)] 秒后，点的位置如下（在秒表重置前）：
秒表重置后：
在起始移动后 #cf_span[1.0] 秒：
在起始移动后 #cf_span[1.(3)] 秒（秒表重置后）：
最终，在起始移动后 #cf_span[2] 秒，点回到初始位置。
该过程将无限循环继续。
**Definitions**
Let $ T = (V, E) $ be a tree with $ n $ vertices, $ V = \{1, 2, \dots, n\} $, and $ |E| = n-1 $. All edges have unit length.
Let $ \mathcal{P} = \{P_1, P_2, \dots, P_k\} $ be a set of simple paths in $ T $ such that:
- $ P_i \cap P_j $ shares no edge for $ i \ne j $ (edge-disjoint),
- $ \bigcup_{P \in \mathcal{P}} V(P) = V $ (vertex-covering).
Each path $ P_i $ is assigned a point moving back-and-forth along it with speed 1 per second, starting at some initial position on the path in a chosen direction.
For each vertex $ v \in V $, define $ \text{res}_v $ as the supremum of times recorded by the stopwatch at $ v $ over infinite motion (reset to 0 every time a point passes through $ v $).
**Constraints**
1. $ 2 \le n \le 100 $
2. The graph is a tree.
**Objective**
Choose $ \mathcal{P} $ and initial point positions/directions to minimize the vector $ (\text{res}_1, \text{res}_2, \dots, \text{res}_n) $ in lexicographic order.