Bobo ma spójny graf nieskierowany $G$ o $n$ wierzchołkach i $m$ krawędziach, którego wierzchołki są dla wygody oznaczone liczbami $1,2,\ldots,n$.

Bobo wybiera niepusty podzbiór krawędzi tak, aby graf z wybranymi krawędziami nadal był spójny. Chciałby poznać liczbę takich podzbiorów modulo $2$.

Przypomnijmy, że graf jest spójny, jeśli dla dowolnych dwóch wierzchołków $a$ i $b$ istnieje ścieżka łącząca $a$ z $b$.

Wejście

Wejście zawiera zero lub więcej przypadków testowych i kończy się wraz z końcem pliku. Dla każdego przypadku testowego:

Pierwszy wiersz zawiera dwie liczby całkowite $n$ i $m$ ($2 \le n \le 2 \cdot 10^5$, $1 \le m \le 2 \cdot 10^5$).

$i$-ty z następnych $m$ wierszy zawiera dwie liczby całkowite $a_i$ i $b_i$, oznaczające krawędź między wierzchołkami $a_i$ i $b_i$.

Zagwarantowano, że suma wszystkich wartości $m$ nie przekracza $2 \cdot 10^5$, a wszystkie podane grafy są spójne.

Wyjście

Dla każdego przypadku testowego wypisz liczbę całkowitą oznaczającą resztę modulo $2$.

Przykład

Wejście 1

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

Wyjście 1

1
1
0