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. It is given in the form of an adjacency list.

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 the integer n.
• The next n lines descibes the adjacent nodes for the i^th node.
  • The first integer m denotes the number of adjacent nodes.
  • The next m integers denote adjacent nodes.

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
3 1 3 6
3 0 2 4
1 1
1 0
2 1 5
1 4
1 0
3
2 1 2
2 0 2
2 0 1
3
1 1
2 0 2
1 1
1
1 0

Expected Output

0
1
0
1

Constraints

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