Keep Moving

Limits: 3s, 512 MB

Balurmath is a city which has N interesting tourist spots, which are connected between themselves by M roads. The roads are directed, which means if there is a road between u and v, it is possible to go from u to v, but not the other way round. Due to ill city-planning, if somebody starts their journey from a particular spot, it is not possible to return to that spot by traveling only through the given roads.

Gubu and Chotu are two eager cats who are playing a game between themselves. They pick a spot X, and both start their tour from this spot. After finishing visiting this spot, Gubu being the big guy decides to visit a spot which can be directly visited right after X by one of the given roads. They both move to the new spot, let’s call it Y. Then Chotu gets to decide the next spot Z which is possible to visit directly after Y though another one of the given roads. Gubu picks the next spot, and they keep playing in turns. He who cannot pick the next possible spot loses.

Gubu is wondering if he can win this game but he is bad at logic, so he is asking for your help. Given X, could you let him know if he is going to win?


Input begins with an integer T (T<=15), number of test cases. Each case contains a line with three integers, N, M and X. Following M lines contain 2 integers each, u,v, which means there is a direct road from spot u to spot v.

1 <= N <= 100000
0 <= M <= 1000000
1 <= u, v, X <= N


For each case, output the case number first, followed by the word ‘Yes’ if Gubu wins this game and ‘No’ if he doesn’t.


Input Output
3 1 0 1 4 4 4 4 1 4 2 4 3 2 3 6 7 3 1 3 3 2 3 4 2 5 4 5 5 6 3 5 Case 1: No Case 2: Yes Case 3: Yes


jabertuhin Earliest, 2017-01-27 04:07:13.671 +0000 UTC

seyedssz Fastest, 0.1s

fahim5466 Lightest, 1.2 MB

seyedssz Shortest, 597B


Login to submit