Problem F
Two-person game

Two children Alice and Bob play the following two-person game: Given an undirected graph $G$ with $n$ nodes and $m$ edges. Each person, in turn, will insert an edge to $G$ if it does not exist. The person who obtains the connected graph after his edge insertion will win the game. Alice will play first. Find out if there is an strategy for Alice to win the game regardless of any strategy played by Bob.

Input

The input consists of several datasets. The first line of the input contains the number of datasets, which is a positive integer and is not greater than 100. The following lines describe the datasets. Each dataset is described by the following lines:

• The first line contains two positive integers $n$ and $m$ ($2\leq n\leq 200, m\leq \frac{n(n-1)}{2}$).

• The $i^{th}$ line in subsequence $m$ lines contains two positive integers $u_ i$ and $v_ i$ representing the $i^{th}$ edge $(u_ i,v_ i)$ of the given graph $G$ ($1\leq i\leq m, 1\leq u_ i,v_ i\leq n, u_ i\neq v_ i$).

Output

The output contains $T$ lines in which the $i^{th}$ line writes the result of $i^{th}$ test with the following format:

• 1 if there is the way for Alice to win the game with any strategy of Bob,

• 0, otherwise.

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

1
0
1
1
0
1