Bobo possède un graphe non orienté connexe $G$ comportant $n$ sommets et $m$ arêtes, dont les sommets sont commodément numérotés $1,2,\ldots,n$.

Bobo choisit un sous-ensemble non vide d'arêtes tel que le graphe formé avec les arêtes choisies reste connexe. Il souhaite connaître le nombre de tels sous-ensembles modulo $2$.

Rappelons qu'un graphe est connexe si, pour deux sommets quelconques $a$ et $b$, il existe un chemin reliant $a$ à $b$.

Entrée

L'entrée contient zéro ou plusieurs cas de test et se termine à la fin du fichier. Pour chaque cas de test :

La première ligne contient deux entiers $n$ et $m$ ($2 \le n \le 2 \cdot 10^5$, $1 \le m \le 2 \cdot 10^5$).

La $i$-ième des $m$ lignes suivantes contient deux entiers $a_i$ et $b_i$ décrivant une arête entre les sommets $a_i$ et $b_i$.

Il est garanti que la somme de tous les $m$ ne dépasse pas $2 \cdot 10^5$ et que tous les graphes donnés sont connexes.

Sortie

Pour chaque cas de test, affichez un entier représentant le reste modulo $2$.

Exemples

Entrée 1

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

Sortie 1

1
1
0