You need to complete n courses to finish a program. The courses are labeled from 0 to n-1.

Each course can have some other courses as prerequisite. You need to find if there exists a valid order in which you take take all the courses to finish the program.

You are given a list prerequisites of size m.
prerequisites[i] = [xi, yi]. You have to take yi before xi.

Return if it is possible to complete the program.

Example

Testing

Input Format

The first line contains an integer T denoting the number of test cases.

For each test case, the input has the following lines:

• The first line contains two space-separated integers n and m.
• The next m lines contains two space-separated integers x_i and y_i.

Output Format

For each test case, the output has one line with 1 or 0, depending on whether you can complete the program or not.

Sample Input

4
6 6
1 0
2 0
3 1
4 3
5 4
4 2
6 7
1 0
2 0
3 1
4 3
5 4
4 2
2 5
2 2
0 1
1 0
3 3
0 1
1 2
0 2

Expected Output

1
0
0
1

Constraints

1 <= T <= 40
1 <= n <= 2000
0 <= m <= 3*104
0 <= xi, yi < n
xi != yi
All [xi, yi] pairs are unique.