Given an undirected graph, find if it has any cycle?
A graph is cyclic, if you can start at a node in the graph, traverse along its edges, and return to the same initial node.

The graph has n nodes indexed 0 to n-1. The graph has m edges and you are given a list of them.

edgesi = [x, y] where x and y are node indices.

Return if it is cyclic or not.

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 descibes the edges of the graph with two space-separated integers - x and y

Output Format

For each test case, the output has one line with 1 or 0, depending on whether the graph is cyclic or not.

Sample Input

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

Expected Output

0
1
0
1

Constraints

1 <= T <= 20
1 <= n <= 500
0 <= m <= 100000