Bobo has a connected undirected graph $G$ with $n$ vertices and $m$ edges where vertices are conveniently labeled with $1, 2, \ldots, n$.

Bobo chooses a non-empty subset of edges such that the graph with the chosen edges is still connected. He would like to know the number of such subsets modulo $2$.

Note that a graph is connected if, for any two vertices $a$ and $b$, there exists a path which connects $a$ and $b$.

Input

The input contains zero or more test cases, and is terminated by end-of-file. For each test case:

The first line contains two integers $n$ and $m$ ($2 \le n \le 2 \cdot 10^5$, $1 \le m \le 2 \cdot 10^5$).

The $i$-th of the following $m$ lines contains two integers $a_i$ and $b_i$ which denote an edge between vertices $a_i$ and $b_i$.

It is guaranteed that the sum of all $m$ does not exceed $2 \cdot 10^5$, and all the given graphs are connected.

Output

For each test case, output an integer which denotes the remainder modulo $2$.

Examples

Input 1

2 1
1 2
3 2
1 2
2 3
3 3
1 2
2 3
3 1

Output 1

1
1
0