CF360E Levko and Game

Levko loves sports pathfinding competitions in his city very much. In order to boost his performance, Levko spends his spare time practicing. The practice is a game. The city consists of $ n $ intersections connected by $ m+k $ directed roads. Two or more roads can connect the same pair of intersections. Besides, there can be roads leading from an intersection to itself. Levko and Zenyk are playing a game. First Levko stands on intersection $ s_{1} $ , and Zenyk stands on intersection $ s_{2} $ . They both want to get to intersection $ f $ . The person who does it quicker wins. If they get there at the same time, the game ends with a draw. By agreement both players start simultaneously and move with the same speed. Levko wants to win very much. He knows the lengths of all the roads in the city. Also he knows that he can change the lengths of some roads (there are $ k $ such roads at all) if he pays the government. So, the government can change the length of the $ i $ -th road to any integer value in the segment \[ $ l_{i} $ , $ r_{i} $ \] (both borders inclusive). Levko wondered if he can reconstruct the roads so as to win the game and whether he can hope for the draw if he cannot win. You should consider that both players play optimally well. It is guaranteed that we can get from intersections $ s_{1} $ and $ s_{2} $ to intersection $ f $ .

N/A

N/A