Urpal lives in a big city. He has planned to meet his lover tonight.

The city has n junctions numbered from 1 to n. The junctions are connected by m directed streets, all the roads have equal length. Urpal lives in junction a and the date is planned in a restaurant in junction b. He wants to use public transportation to get to junction b. There are k bus transportation companies. At the beginning of every second, a bus from the i-th company chooses a random shortest path between junction s_i and junction t_i and passes through it. There might be no path from s_i to t_i. In that case no bus will leave from s_i to t_i. If a bus passes through a junction where Urpal stands, he can get on the bus. He can also get off the bus at any junction along the path.

Now Urpal wants to know if it's possible to go to the date using public transportation in a finite amount of time (the time of travel is the sum of length of the traveled roads) and what is the minimum number of buses he should take in the worst case.

At any moment Urpal knows only his own position and the place where the date will be. When he gets on the bus he knows only the index of the company of this bus. Of course Urpal knows the city map and the the pairs (s_i, t_i) for each company.

Note that Urpal doesn't know buses velocity.