第二学期在巴甫洛波利斯大学开始。在维克波利斯度假后,努拉需要返回巴甫洛波利斯并继续她的学习。
有时(或经常)有些老师不喜欢你。顺便说一句,Noora 也有一位这样的老师。他的名字叫尤里·德米特里耶维奇(Yury Dmitrievich),教授图论。尤里·德米特里耶维奇不喜欢努拉,所以他总是给这个女孩布置最困难的任务。所以这次就出事了。
老师给了 Noora 一棵有 n 个顶点的树。顶点用 1 到 n 之间的整数进行编号。这棵树所有边的长度都是 1。Noora 选择一组成对在边上不相交的简单路径。然而,每个顶点应至少属于所选路径之一。
对于每个选定的路径,执行以下操作:
1. 我们选择属于该路径的一条边 (u, v)。
2. 在选定的边 (u, v) 上,有一个点位于距顶点 u 的选定距离 x 处,距顶点 v 的距离 1 - x 处。但是 Noora 任意选择距离 x,i。 e.对于不同的边缘它可以是不同的。
3. 选择顶点 u 或 v 之一。该点将开始移动到选定的顶点。
让我们通过例子解释一下点是如何移动的。假设路径由两条边 (v1, v2) 和 (v2, v3) 组成,该点最初位于边 (v1, v2) 上并开始移动到顶点 v1。然后该点将到达v1,然后“掉头”,因为到达了路径的终点,进一步它将向另一个方向移动到顶点v2,然后到顶点v3,然后再次“掉头”,然后移动到v2,依此类推。点的速度为每秒 1 个边缘。例如,在 0.5 秒内,点移动到边缘一半的长度。
在树的每个顶点放置一个秒表。开始时秒表指示的时间为 0 秒。然后在开始时刻,所有点同时开始沿着选定路径从选定位置向选定方向移动,并且秒表同时启动。当其中一点到达顶点 v 时,顶点 v 处的秒表自动重置,即从零开始计时。
resv 表示如果点运动无限继续,顶点 v 处的秒表将显示的最长时间。 Noora 被要求选择路径和路径上的点,以使 res1 尽可能小。如果有多种解决方案可以做到这一点,则需要最小化res2,然后是res3,res4,...,resn。
帮助Noora完成老师的任务。
为了更好地理解该语句,请参阅示例的解释。
输入
第一行包含单个整数 n (2 ≤ n ≤ 100) — 给定树中的顶点数。
接下来的 n - 1 行中的每一行都包含两个整数 u 和 v (1 ≤ u, v ≤ n, u ≠ v) — 由边连接的顶点。
保证输入定义有效的树。
输出
在第一行打印单个整数路径 - 您要选择的路径数。
在接下来的路径行中打印路径的描述:
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(与第三段中第一个打印的顶点相同)之间的距离。
示例
输入 #1
3 1 2 2 3
输出 #1
2 1 1 1 2 0.6666666666 1 2 2 3 0.6666666666
注意
评分:
裁判系统将使用参赛者提供的输出数据生成数组资源。此外,系统将根据陪审团的回答生成数组 resOptimal。如果仅对于每个 i (1 ≤ i ≤ n) 满足以下条件,您的答案将被接受:$$\frac{|res_i - resOptimal_i|}{max(1, resOptimal_i)} \leq 10^{-6}$$。
考虑一个例子。
在开始时刻时间点的位置如下:
第一条路径以红色突出显示,第二条路径以蓝色突出显示,绿色圆圈代表所选点,顶点内的棕色数字 - 秒表的当前时间。紫色箭头表示点移动的方向。
在 0.(3) 秒内,点将按以下方式定位(在秒表重置之前):
秒表重置后:
移动开始后 1.0 秒内:
开始移动后 1.(3) 秒内(秒表重置后):
最后,在开始移动后的2秒内点返回到其初始位置。
这个过程将无限地持续下去。