Тони Старк играет со своими костюмами, которые теперь оснащены автопилотом. Он живёт в Малибу. Малибу представляет из себя n перекрёстков, пронумерованных целыми числами от 1 до n, соединённых с помощью n - 1 двусторонних дорог таким образом, что от любого перекрёстка можно добраться до любого другого, используя данные дороги (да, граф Малибу является деревом).
У Тони есть m костюмов, для каждого из которых разработан специальный план. Костюм номер i появится в момент времени ti на перекрёстке vi и будет двигаться в направлении перекрёстка ui по кратчайшему пути со скоростью ci дорог в секунду (пересечение перекрёстка происходит мгновенно), а затем исчезнет, как только достигнет перекрёстка ui. Если костюм достигает перекрёстка ui непосредственно в момент времени q, то он доступен там в этот момент времени, но не позже. Костюмы передвигаются непрерывно, например, если vi ≠ ui, то в момент времени 
костюм находится на середине дороги. Обратите внимание, что vi = ui означает, что костюм будет доступен на перекрёстке vi только в момент времени ti и затем исчезнет.
Если в какой-либо момент времени два костюма оказываются в одной точке (это может быть как на перекрёстке, так и на какой-нибудь дороге непосредственно после появления или перед исчезновением), то там происходит взрыв.
Тони просит вас определить момент самого первого взрыва (если это вообще произойдёт).
В первой строке входных данных записаны два целых числа n и m (1 ≤ n, m ≤ 100 000) — количество перекрёстков и количество костюмов соответственно.
В последующих n - 1 строках содержится описание дорог. В i-й из этих строк содержится два целых числа 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-й костюм появится на перекрёстке vi в момент времени ti и будет двигаться в сторону перекрёстка ui со скоростью ci дорог в секунду.
Если никаких взрывов так и не произойдёт, то выведите -1 в первой и единственной строке входных данных.
В противном случае выведите момент времени первого взрыва. Ваш ответ будет считаться правильным, если его относительная или абсолютная погрешность не превзойдёт 10 - 6.
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
27.3
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
-1
| Codeforces Round 366 (Div. 1) |
|---|
| Закончено |
