CF567E President and Roads

Berland has $ n $ cities, the capital is located in city $ s $ , and the historic home town of the President is in city $ t $ ( $ s≠t $ ). The cities are connected by one-way roads, the travel time for each of the road is a positive integer. Once a year the President visited his historic home town $ t $ , for which his motorcade passes along some path from $ s $ to $ t $ (he always returns on a personal plane). Since the president is a very busy man, he always chooses the path from $ s $ to $ t $ , along which he will travel the fastest. The ministry of Roads and Railways wants to learn for each of the road: whether the President will definitely pass through it during his travels, and if not, whether it is possible to repair it so that it would definitely be included in the shortest path from the capital to the historic home town of the President. Obviously, the road can not be repaired so that the travel time on it was less than one. The ministry of Berland, like any other, is interested in maintaining the budget, so it wants to know the minimum cost of repairing the road. Also, it is very fond of accuracy, so it repairs the roads so that the travel time on them is always a positive integer.

N/A

N/A

The cost of repairing the road is the difference between the time needed to ride along it before and after the repairing. In the first sample president initially may choose one of the two following ways for a ride: $ 1→2→4→5→6 $ or $ 1→2→3→5→6 $ .