You are given an undirected graph with n nodes, indexed 0 to n-1.
You are given the adjacency list representation of the graph.

You have to find if the given graph is bipartite.

A graph is bipartite if the nodes can be partitioned into two independent sets X and Y such that every edge in the graph connects a node in set X and a node in set Y.

Example 1

n: 4
adjList: [[1, 3], [0, 2, 3], [1, 3], [0, 1, 2]]
Is Bipartite: False
Explanation: There is no way to partition the nodes into two independent sets such that every edge connects a node in one and a node in the other.

Example 2

n: 4
adjList: [[1, 3], [0, 2], [1, 3], [0, 2]]
Is Bipartite: True
Explanation: We can partition them into {0, 2}, {1, 3}.

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, based on whether the graph is bipartite or not.

Sample Input

4
4
2 1 3
3 0 2 3
2 1 3
3 0 1 2
4
2 1 3
2 0 2
2 1 3
2 0 2
1
1 0
2
1 1
1 0

Expected Output

0
1
0
1

Constraints

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