시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
3 초 | 512 MB | 74 | 38 | 25 | 58.140% |
In ICPCCamp there are $n$ cities which are conveniently labeled with $1, 2, \dots, n$. There are also $m$ bidirectional roads: the $i$-th road connects cities $a_i$ and $b_i$.
Bobo chooses a non-empty subset of cities to form a union. For each two cities $a$ and $b$ in the union, there must exist a path from $a$ to $b$ passing through no cities outside the union. In other words, the union must be connected.
Bobo would like to know how many ways there are to choose such a subset, but he is afraid of large numbers. Therefore, he just wants to find this number modulo $2$.
The first line contains two integers $n$ and $m$ ($1 \leq n \leq 50$, $0 \leq m \leq \frac{n(n - 1)}{2}$).
The $i$-th of the following $m$ lines contains two integers $a_i$ and $b_i$ ($1 \leq a_i, b_i \leq n$, $0 < |a_i - b_i| \leq 13$).
Output an integer which denotes the number of possible subsets modulo $2$.
3 2 1 2 2 3
0
3 3 1 2 2 3 3 1
1