Problem A
From D to E and back
Input: Standard Input

Output: Standard Output

Samuel Goldwyn

Take any directed graph D with n vertices and m edges. You can make the Lying graph E of D in the following way. E will have m vertices, one for each edge of D. For example, if D has an edge uv, then E will have a vertex called uv. Now, whenever D has edges uv and vw, E will have an edge from vertex uv to vertex vw. There are no other edges in E.

You will be given a graph E and will have to determine whether it is possible for E to be the Lying graph of some directed graph D.

Input

The first line of input gives the number of cases, N (N<220). N test cases follow. Each one starts with two lines containing m (0≤m≤300) and k. The next k lines will each contain a pair of vertices, x and y, meaning that there is an edge from x to y in E. The vertices are numbered from 0 to m-1

Output

For each test case, output one line containing "Case #x:" followed by either "Yes" or "No", depending on whether E is a valid Lying graph or not. Note that D is allowed to have duplicate edges and self-edges.

Sample Input                                  Output for Sample Input

4

2

1

0 1

5

0

4

3

0 1

2 1

2 3

3

9

0 1

0 2

1 2

1 0

2 0

2 1

0 0

1 1

2 2

Case #1: Yes

Case #2: Yes

Case #3: No

Case #4: Yes

Problem setter: Igor Naverniouk

Special Thanks: Joachim Wulff