Description
Given a directed acyclic graph of N nodes, two players take turn to pick a valid node to visit, starting from node number 1. A valid node v is a node which is connected by the current one u (there is an edge from u to v). If a player reaches the ending point, node number N, then he or she wins the game. Determine whether the player who moves first can win or not, assuming both taking the best strategies.
For example, consider the following graph, the best way to win if you move first is to move to node number 2 from the starting point. Your opponent have no choice but to move to node number 3, and you win the game by moving to the end point after that.
.png)
Figure. An example of the game
Input
There are serveral test cases in the input. Each case starts with two integers N (2 ≤ N ≤ 5000) and M (M ≤ 60000), denoting the number of nodes and the number of edges in the graph. Each of the next M lines contains two integers u and v (u ≠ v), indicating a directed edge from u to v. It is guaranteed that there is at most one edge from u to v. Moreover, there will be no edge ending at the starting point and starting from the ending point (i.e. (u, 1) and (N, v) does not exist). The number of test cases will be no more than 100, and the input is terminated by N = M = 0.
Hint: Using adjacency lists to store the graph is recommended.
Output
For each test case, output a line contains “Case i:” and then “Yes” or “No” to indicate whether it is possible or not to win the game if you move first. i is the number of test case starting from 1.