시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 11 | 7 | 7 | 63.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$.
2 1 1 2 3 2 1 2 2 3 3 3 1 2 2 3 3 1
1 1 0