시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB117763.636%

문제

Bobo has a connected undirected graph $G$ with $n$ vertices and $m$ edges where vertices are conveniently labeled with $1, 2, \dots, 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$.

입력

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 \leq n \leq 2 \cdot 10^5$, $1 \leq m \leq 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.

출력

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

예제 입력 1

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

예제 출력 1

1
1
0