CF704E Iron Man

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

N/A

N/A