시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 512 MB 1 1 1 100.000%

문제

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$.

예제 입력 1

3 2
1 2
2 3

예제 출력 1

0

예제 입력 2

3 3
1 2
2 3
3 1

예제 출력 2

1