Tianjin University Online Judge
Contests Virtual Contests Problems Submit Runs Status Rank List Forum

2892.   Task
Time Limit: 1.0 Seconds   Memory Limit: 65536K
Total Runs: 1924   Accepted Runs: 707



Peter is very interested in Artificial Intelligence. His teacher leaves him several problems. Since he is not very familiar with the subject, he will read some necessary information to complete the task. But unfortunately there are some constrains between the problems (that one problem must be done after another one). Please write a program to judge whether Peter can complete the task.

Input

There are several test cases in the input data. The first line contains the number of test cases. In each test case, the first line contains two positive integers n (1 ≤ n ≤ 20) and m (0 ≤ m ≤ 20), denoting that there are n problems and m constrains. Then there are m lines to describe the constrains, and each line contains two different integers i and j (1 ≤ i, j ≤ n), denoting that the problem j must be done after the problem i. (The problems' number starts at 1.)

Output

Please write a program to judge whether Peter can complete the task. If he can, please output "1"; otherwise output "0" instead.

Sample Input

2
3 2
1 2
1 3
3 3
1 2
2 3
3 1

Sample Output

1
0


Source: TJU Exam 2007
Submit   List    Runs   Forum   Statistics

Tianjin University Online Judge v1.3.0
Maintance:G.D.Retop. Developer: SuperHacker, G.D.Retop