CF822F.Madness

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.

第二学期在帕夫洛波利斯大学开始了。假期结束后，诺拉需要从维奇科波利斯返回帕夫洛波利斯，继续她的学业。

有时（或者相当频繁地）会出现一些不喜欢你的老师。巧合的是，诺拉也有一位这样的老师。他的名字是尤里·德米特里耶维奇，教授图论课程。尤里·德米特里耶维奇不喜欢诺拉，因此总是给她布置最难的任务。这次也不例外。

老师给了诺拉一棵含有 $ n $ 个顶点的树。顶点用整数 $ 1 $ 到 $ n $ 编号。该树的所有边长度均为 $ 1 $。诺拉需选择一组两两边不相交的简单路径，使得每个顶点至少属于其中一条所选路径。

对每条所选路径，执行如下操作：

1. 在该路径中恰好选择一条边 $ (u,,v) $；
2. 在所选边 $ (u,,v) $ 上选取一点，该点到顶点 $ u $ 的距离为某个选定值 $ x $，到顶点 $ v $ 的距离则为 $ 1 - x $。但诺拉可任意选定该距离 $ x $，即不同边上的 $ x $ 值可以互不相同；
3. 在顶点 $ u $ 和 $ v $ 中任选其一；该点将从此刻起朝所选顶点方向开始移动。

下面通过一个例子说明点的运动方式：假设路径由两条边 $ (v_1,,v_2) $ 和 $ (v_2,,v_3) $ 构成，点初始位于边 $ (v_1,,v_2) $ 上，并开始向顶点 $ v_1 $ 移动。那么该点将先抵达 $ v_1 $，随后因已到达路径端点而“折返”，接着沿相反方向移向顶点 $ v_2 $，再移向 $ v_3 $，再次“折返”，然后移向 $ v_2 $，如此往复。所有点的运动速度均为每秒 1 条边。例如，在 $ 0.5 $ 秒内，点将移动半条边的长度。

树的每个顶点上均放置一个秒表。初始时刻（$ t = 0 $ 秒），所有秒表显示的时间均为 $ 0 $ 秒。在初始时刻，所有点同时从各自选定的位置、按各自选定的方向，沿各自所属路径开始运动，且所有秒表也同时启动。当某一点到达顶点 $ v $ 时，顶点 $ v $ 处的秒表会自动复位，即重新从零开始计时。

记 $ res_v $ 为：若点的运动无限持续下去，顶点 $ v $ 处秒表所显示过的最大时间值。诺拉的任务是选择路径及各路径上的点，使得 $ res_1 $ 尽可能小。若存在多个使 $ res_1 $ 最小的方案，则需进一步使 $ res_2 $ 最小；若仍有多个方案，则继续使 $ res_3 $ 最小，依此类推，直至 $ res_n $。

请帮助诺拉完成老师的这项任务。

为更好理解题意，请参阅示例的详细解释。

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.

第一行包含一个整数 $n$（$2 \leq n \leq 100$）—— 给定树中的顶点数。

接下来的 $n-1$ 行中，每行包含两个整数 $u$ 和 $v$（$1 \leq u, v \leq n$，$u \neq v$）—— 由一条边连接的两个顶点。

保证输入数据定义了一棵合法的树。

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).

第一行输出一个整数 paths —— 表示你希望选择的路径数量。

接下来的 paths 行依次描述每条路径：

1. 一个整数 len —— 当前路径中边的数量。
2. len 个整数 —— 路径中各边的编号。边按输入中给出的顺序从 1 到 n - 1 编号。
3. 两个整数 u 和 v —— 表示你在顶点 u 与 v 之间的边上放置一个点（显然该边必须属于当前路径），且该点将向顶点 v 移动。注意：此处边端点的输出顺序至关重要。例如，若你输出 "1 2"（不带引号），则该点将向顶点 2 移动；而若你输出 "2 1"（不带引号），则该点将向顶点 1 移动。
4. 一个实数 x（满足 0 ≤ x ≤ 1）—— 表示该点到顶点 u 的距离（即第 3 步中首先输出的那个顶点）。

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.

考虑一个例子。

在初始时刻，各点的位置如下所示：

第一条路径以红色高亮显示，第二条路径以蓝色高亮显示；绿色圆圈表示所选的点；顶点内部的棕色数字表示秒表当前显示的时间；紫色箭头表示点将要移动的方向。

在 $0.\overline{3}$ 秒后（秒表重置前），各点位置如下：

秒表重置后：

开始运动后 $1.0$ 秒时：

开始运动后 $1.\overline{3}$ 秒时（秒表重置后）：

最终，在开始运动后 $2$ 秒时，各点回到初始位置：

该过程将无限重复下去。