There are n cities in Berland. Some pairs of them are connected with m directed roads. One can use only these roads to move from one city to another. There are no roads that connect a city to itself. For each pair of cities (x, y) there is at most one road from x to y.
A path from city s to city t is a sequence of cities p1, p2, … , pk, where p1 = s, pk = t, and there is a road from city pi to city pi + 1 for each ifrom 1 to k - 1. The path can pass multiple times through each city except t. It can’t pass through t more than once.more >>