English · Original
Chinese · Translation
Formal · Original
Tony Stark is playing a game with his suits (they have auto-pilot now). He lives in Malibu. Malibu has _n_ junctions numbered from 1 to _n_, connected with _n_ - 1 roads. One can get from a junction to any other junction using these roads (graph of Malibu forms a tree).
Tony has _m_ suits. There's a special plan for each suit. The _i_\-th suit will appear at the moment of time _t__i_ in the junction _v__i_, and will move to junction _u__i_ using the shortest path between _v__i_ and _u__i_ with the speed _c__i_ roads per second (passing a junctions takes no time), and vanishing immediately when arriving at _u__i_ (if it reaches _u__i_ in time _q_, it's available there at moment _q_, but not in further moments). Also, suits move continuously (for example if _v__i_ ≠ _u__i_, at time it's in the middle of a road. Please note that if _v__i_ = _u__i_ it means the suit will be at junction number _v__i_ only at moment _t__i_ and then it vanishes.
An explosion happens if at any moment of time two suits share the same exact location (it may be in a junction or somewhere on a road; while appearing, vanishing or moving).
Your task is to tell Tony the moment of the the first explosion (if there will be any).
## Input
The first line of the input contains two integers _n_ and _m_ (1 ≤ _n_, _m_ ≤ 100 000) — the number of junctions and the number of suits respectively.
The next _n_ - 1 lines contain the roads descriptions. Each line contains two integers _a__i_ and _b__i_ — endpoints of the _i_\-th road (1 ≤ _a__i_, _b__i_ ≤ _n_, _a__i_ ≠ _b__i_).
The next _m_ lines contain the suit descriptions. The _i_\-th of them contains four integers _t__i_, _c__i_, _v__i_ and _u__i_ (0 ≤ _t__i_ ≤ 10 000, 1 ≤ _c__i_ ≤ 10 000, 1 ≤ _v__i_, _u__i_ ≤ _n_), meaning the _i_\-th suit will appear at moment of time _t__i_ at the junction _v__i_ and will move to the junction _u__i_ with a speed _c__i_ roads per second.
## Output
If there would be no explosions at all, print _\-1_ in the first and only line of output.
Otherwise print the moment of the first explosion.
Your answer will be considered correct if its relative or absolute error doesn't exceed 10 - 6.
[samples]
托尼·斯塔克正在与他的战衣（现在具有自动驾驶功能）玩游戏。他住在马里布。马里布有 #cf_span[n] 个交叉口，编号从 #cf_span[1] 到 #cf_span[n]，由 #cf_span[n - 1] 条道路连接。通过这些道路，可以从任意一个交叉口到达其他任意交叉口（马里布的图结构是一棵树）。
托尼有 #cf_span[m] 套战衣。每套战衣都有一个特定的计划。第 #cf_span[i] 套战衣将在时刻 #cf_span[ti] 出现在交叉口 #cf_span[vi]，并以每秒 #cf_span[ci] 条道路的速度，沿着 #cf_span[vi] 和 #cf_span[ui] 之间的最短路径移动到交叉口 #cf_span[ui]（经过交叉口不耗时），并在到达 #cf_span[ui] 时立即消失（如果它在时刻 #cf_span[q] 到达 #cf_span[ui]，则它在时刻 #cf_span[q] 可用，但在之后的时刻不可用）。此外，战衣的移动是连续的（例如，若 #cf_span[vi ≠ ui]，则在时刻 #cf_span[t] 它位于某条道路的中点）。请注意，若 #cf_span[vi = ui]，则表示该战衣仅在时刻 #cf_span[ti] 位于交叉口 #cf_span[vi]，随后立即消失。
当任意时刻有两套战衣处于完全相同的位置时（可能在交叉口，也可能在道路的某处；包括出现、消失或移动过程中），会发生爆炸。
你的任务是告诉托尼第一次爆炸发生的时刻（如果有的话）。
输入的第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n, m ≤ 100 000]）——分别表示交叉口数量和战衣数量。
接下来的 #cf_span[n - 1] 行描述道路。每行包含两个整数 #cf_span[ai] 和 #cf_span[bi]——第 #cf_span[i] 条道路的两个端点（#cf_span[1 ≤ ai, bi ≤ n]，#cf_span[ai ≠ bi]）。
接下来的 #cf_span[m] 行描述战衣。第 #cf_span[i] 行包含四个整数 #cf_span[ti]、#cf_span[ci]、#cf_span[vi] 和 #cf_span[ui]（#cf_span[0 ≤ ti ≤ 10 000，1 ≤ ci ≤ 10 000]，#cf_span[1 ≤ vi, ui ≤ n]），表示第 #cf_span[i] 套战衣将在时刻 #cf_span[ti] 出现在交叉口 #cf_span[vi]，并以每秒 #cf_span[ci] 条道路的速度移动到交叉口 #cf_span[ui]。
如果没有爆炸发生，请在第一行且仅有一行中输出 _-1_。
否则，请输出第一次爆炸发生的时刻。
你的答案只要相对误差或绝对误差不超过 #cf_span[10 - 6]，即被视为正确。
## Input
输入的第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n, m ≤ 100 000]）——分别表示交叉口数量和战衣数量。接下来的 #cf_span[n - 1] 行描述道路。每行包含两个整数 #cf_span[ai] 和 #cf_span[bi]——第 #cf_span[i] 条道路的两个端点（#cf_span[1 ≤ ai, bi ≤ n]，#cf_span[ai ≠ bi]）。接下来的 #cf_span[m] 行描述战衣。第 #cf_span[i] 行包含四个整数 #cf_span[ti]、#cf_span[ci]、#cf_span[vi] 和 #cf_span[ui]（#cf_span[0 ≤ ti ≤ 10 000，1 ≤ ci ≤ 10 000]，#cf_span[1 ≤ vi, ui ≤ n]），表示第 #cf_span[i] 套战衣将在时刻 #cf_span[ti] 出现在交叉口 #cf_span[vi]，并以每秒 #cf_span[ci] 条道路的速度移动到交叉口 #cf_span[ui]。
## Output
如果没有爆炸发生，请在第一行且仅有一行中输出 _-1_。否则，请输出第一次爆炸发生的时刻。你的答案只要相对误差或绝对误差不超过 #cf_span[10 - 6]，即被视为正确。
[samples]
**Definitions**
Let $ n, m \in \mathbb{Z}^+ $ denote the number of junctions and suits, respectively.
Let $ T = (V, E) $ be a tree with $ |V| = n $, $ |E| = n-1 $, where each edge has unit length.
For each suit $ i \in \{1, \dots, m\} $:
- $ t_i \in \mathbb{R}_{\geq 0} $: appearance time,
- $ c_i \in \mathbb{R}^+ $: speed (roads per second),
- $ v_i, u_i \in V $: start and end junctions.
Let $ d(x, y) $ denote the shortest-path distance (number of edges) between nodes $ x, y \in V $.
Let $ L_i = d(v_i, u_i) $: total path length for suit $ i $.
Let $ \tau_i = t_i + \frac{L_i}{c_i} $: vanishing time of suit $ i $.
For suit $ i $, its position at time $ \theta \in [t_i, \tau_i] $ is a point along the unique path from $ v_i $ to $ u_i $, at fractional distance $ \frac{c_i(\theta - t_i)}{L_i} $ from $ v_i $ toward $ u_i $.
**Constraints**
1. $ 1 \leq n, m \leq 100{,}000 $
2. $ 0 \leq t_i \leq 10{,}000 $, $ 1 \leq c_i \leq 10{,}000 $, $ 1 \leq v_i, u_i \leq n $
3. The graph is a tree.
**Objective**
Find the minimal $ \theta \geq 0 $ such that two suits $ i \ne j $ occupy the same point in the tree at time $ \theta $, i.e., their continuous trajectories intersect in space-time:
$$
\exists i < j \text{ such that } \theta \in [t_i, \tau_i] \cap [t_j, \tau_j] \text{ and } \text{pos}_i(\theta) = \text{pos}_j(\theta)
$$
If no such $ \theta $ exists, output $ -1 $.
API Response (JSON)
{
"problem": {
"name": "E. Iron Man",
"description": {
"content": "Tony Stark is playing a game with his suits (they have auto-pilot now). He lives in Malibu. Malibu has _n_ junctions numbered from 1 to _n_, connected with _n_ - 1 roads. One can get from a junction t",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 5000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF704E"
},
"statements": [
{
"statement_type": "Markdown",
"content": "Tony Stark is playing a game with his suits (they have auto-pilot now). He lives in Malibu. Malibu has _n_ junctions numbered from 1 to _n_, connected with _n_ - 1 roads. One can get from a junction t...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "托尼·斯塔克正在与他的战衣（现在具有自动驾驶功能）玩游戏。他住在马里布。马里布有 #cf_span[n] 个交叉口，编号从 #cf_span[1] 到 #cf_span[n]，由 #cf_span[n - 1] 条道路连接。通过这些道路，可以从任意一个交叉口到达其他任意交叉口（马里布的图结构是一棵树）。\n\n托尼有 #cf_span[m] 套战衣。每套战衣都有一个特定的计划。第 #cf_span[i...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n, m \\in \\mathbb{Z}^+ $ denote the number of junctions and suits, respectively. \nLet $ T = (V, E) $ be a tree with $ |V| = n $, $ |E| = n-1 $, where each edge has unit length....",
"is_translate": false,
"language": "Formal"
}
]
}