托尼·斯塔克正在用他的套装玩游戏(它们现在有自动驾驶仪)。他住在马里布。马里布有n个路口,编号从1到n,与n-1条道路相连。人们可以使用这些道路从一个路口到达任何其他路口(马里布的图形形成一棵树)。
托尼有m套套装。每套西装都有一个特殊的计划。第 i 个衣服将在时间 ti 出现在交汇点 vi 中,并使用 vi 和 ui 之间的最短路径以每秒 ci 路的速度移动到交汇点 ui(通过交汇点不需要时间),并在到达 ui 时立即消失(如果在时间 q 到达 ui,则在 q 时刻可用,但在以后的时刻不再可用)。另外,花色会连续移动(例如,如果 vi ≠ ui,则在时间 $${ t _ { i } + \frac { 1 } { 2 c _ { i } } }$$ 时,花色位于路中间。请注意,如果 vi = ui,则意味着花色仅在时刻 ti 位于交汇处 vi 处,然后消失。
如果在任何时刻两套套装共享相同的确切位置(可能在路口或道路上的某个地方;出现、消失或移动时),就会发生爆炸。
你的任务是告诉托尼第一次爆炸的时刻(如果有的话)。
输入
输入的第一行包含两个整数 n 和 m (1 ≤ n, m ≤ 100 000)——分别是连接点的数量和花色的数量。
接下来的 n - 1 行包含道路描述。每行包含两个整数 ai 和 bi - 第 i 条路的端点(1 ≤ ai,bi ≤ n,ai ≠ bi)。
接下来的 m 行包含套装描述。其中第 i 个包含四个整数 ti、ci、vi 和 ui(0 ≤ ti ≤ 10 000、1 ≤ ci ≤ 10 000、1 ≤ vi、ui ≤ n),这意味着第 i 个花色将在 ti 时刻出现在交叉点 vi 处,并以每秒 ci 条路的速度移动到交叉点 ui。
输出
如果根本不会发生爆炸,请在输出的第一行也是唯一一行中打印 -1。
否则打印第一次爆炸的时刻。
如果您的答案的相对或绝对误差不超过 10 - 6,则视为正确。
示例
输入 #1
6 4 2 5 6 5 3 6 4 6 4 1 27 6 1 3 9 5 1 6 27 4 3 4 11 29 2 6
输出 #1
27.3
输入 #2
6 4 3 1 4 5 6 4 6 1 2 6 16 4 4 5 13 20 6 2 3 16 4 5 28 5 3 5
输出 #2
-1