Contests | Virtual Contests | Problems | Submit | Runs Status | Rank List | Forum |

Time Limit: 1.0 Seconds Memory Limit: 65536K

Total Runs: 1930 Accepted Runs: 709

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

Maintance:G.D.Retop. Developer: SuperHacker, G.D.Retop