Bobo hat einen zusammenhängenden ungerichteten Graphen $G$ mit $n$ Knoten und $m$ Kanten, dessen Knoten praktischerweise mit $1,2,\ldots,n$ beschriftet sind.

Bobo wählt eine nichtleere Teilmenge der Kanten so aus, dass der Graph mit den gewählten Kanten weiterhin zusammenhängend ist. Er möchte die Anzahl solcher Teilmengen modulo $2$ wissen.

Beachte, dass ein Graph zusammenhängend ist, wenn es für je zwei Knoten $a$ und $b$ einen Pfad gibt, der $a$ und $b$ verbindet.

Eingabe

Die Eingabe enthält null oder mehr Testfälle und endet mit dem Dateiende. Für jeden Testfall gilt:

Die erste Zeile enthält zwei ganze Zahlen $n$ und $m$ ($2 \le n \le 2 \cdot 10^5$, $1 \le m \le 2 \cdot 10^5$).

Die $i$-te der folgenden $m$ Zeilen enthält zwei ganze Zahlen $a_i$ und $b_i$, die eine Kante zwischen den Knoten $a_i$ und $b_i$ angeben.

Es ist garantiert, dass die Summe aller $m$ den Wert $2 \cdot 10^5$ nicht überschreitet und alle gegebenen Graphen zusammenhängend sind.

Ausgabe

Gib für jeden Testfall eine ganze Zahl aus, die den Rest modulo $2$ angibt.

Beispiele

Eingabe 1

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

Ausgabe 1

1
1
0