Bobo tiene un grafo no dirigido y conexo $G$ con $n$ vértices y $m$ aristas, cuyos vértices están numerados del $1$ al $n$.

Bobo elige un subconjunto no vacío de aristas de modo que el grafo formado por las aristas elegidas siga siendo conexo. Quiere saber cuántos subconjuntos de este tipo hay, módulo $2$.

Recuerda que un grafo es conexo si, para cualesquiera dos vértices $a$ y $b$, existe un camino que conecta $a$ con $b$.

Entrada

La entrada contiene cero o más casos de prueba y termina al llegar al fin de archivo. Para cada caso de prueba:

La primera línea contiene dos enteros $n$ y $m$ ($2 \le n \le 2 \cdot 10^5$, $1 \le m \le 2 \cdot 10^5$).

La $i$-ésima de las siguientes $m$ líneas contiene dos enteros $a_i$ y $b_i$ que indican una arista entre los vértices $a_i$ y $b_i$.

Se garantiza que la suma de todos los valores de $m$ no supera $2 \cdot 10^5$ y que todos los grafos dados son conexos.

Salida

Para cada caso de prueba, imprime un entero que indique el resto módulo $2$.

Ejemplos

Entrada 1

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

Salida 1

1
1
0