Bobo tem um grafo não direcionado conexo $G$ com $n$ vértices e $m$ arestas, cujos vértices estão convenientemente numerados de $1,2,\ldots,n$.

Bobo escolhe um subconjunto não vazio de arestas de modo que o grafo com as arestas escolhidas continue conexo. Ele gostaria de saber o número desses subconjuntos módulo $2$.

Observe que um grafo é conexo se, para quaisquer dois vértices $a$ e $b$, existe um caminho que conecta $a$ e $b$.

Entrada

A entrada contém zero ou mais casos de teste e termina no fim do arquivo. Para cada caso de teste:

A primeira linha contém dois inteiros $n$ e $m$ ($2\le n\le2\cdot10^5$, $1\le m\le2\cdot10^5$).

A $i$-ésima das próximas $m$ linhas contém dois inteiros $a_i$ e $b_i$, que representam uma aresta entre os vértices $a_i$ e $b_i$.

É garantido que a soma de todos os valores de $m$ não excede $2\cdot10^5$ e que todos os grafos fornecidos são conexos.

Saída

Para cada caso de teste, imprima um inteiro que representa o resto módulo $2$.

Exemplos

Entrada 1

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

Saída 1

1
1
0