Vor einigen Jahren stellte derselbe Autor bei einem Schülerwettbewerb die folgende Aufgabe: Aus einem gegebenen zusammenhängenden ungerichteten Graphen mit Mindestgrad mindestens $2$ sollen zwei benachbarte Knoten so gelöscht werden, dass der Zusammenhang erhalten bleibt. Diese Aufgabe ist für einen Studierendenwettbewerb im Jahr 2020 jedoch zu einfach, also geht es nun weiter.

Gegeben ist ein zusammenhängender ungerichteter Graph mit mindestens $3$ Knoten ohne Schleifen und Mehrfachkanten. Bestimmen Sie für jede Kante, ob der Graph zusammenhängend bleibt, wenn ihre beiden Endknoten gelöscht werden.

Beachten Sie, dass der Graph in dieser Aufgabe Knoten vom Grad $1$ enthalten darf, jedoch keine Knoten vom Grad $0$ (da er zusammenhängend ist und mindestens $3$ Knoten besitzt).

Eingabe

Die erste Eingabezeile enthält zwei ganze Zahlen $n$ und $m$ ($3 \le n \le 3 \cdot 10^5$; $n-1 \le m \le 3 \cdot 10^5$): die Anzahl der Knoten beziehungsweise der Kanten. Die $i$-te der folgenden $m$ Zeilen enthält zwei durch ein Leerzeichen getrennte ganze Zahlen $x$ und $y$: die Endknoten der $i$-ten Kante ($1 \le x,y \le n$; $x \ne y$). Es ist garantiert, dass der Graph zusammenhängend ist und keine Mehrfachkanten enthält.

Ausgabe

Geben Sie eine einzelne Binärzeichenkette der Länge $m$ aus: Das $i$-te Zeichen der Antwort soll 0 (ohne Anführungszeichen) sein, falls das Löschen der Endknoten der $i$-ten Kante den Zusammenhang des Graphen aufhebt, und andernfalls 1.

Beispiele

Eingabe 1

4 4
1 2
2 3
3 1
4 1

Ausgabe 1

0101

Hinweis

Bitte beachten Sie, dass nicht nur die Kante selbst gelöscht wird, sondern auch ihre beiden Endknoten. Daher unterscheidet sich diese Aufgabe vom Finden von Brücken.

Zum Beispiel ist im Beispiel die Kante $1$–$2$ keine Brücke, aber durch das Löschen der Knoten $1$ und $2$ wird der Graph unzusammenhängend: Der entstehende Graph besteht aus zwei isolierten Knoten $3$ und $4$.

Andererseits ist die Kante $1$–$4$ eine Brücke, aber nach dem Löschen der Knoten $1$ und $4$ ist der Graph zusammenhängend: Der entstehende Graph besteht aus zwei Knoten $2$ und $3$, die durch die Kante $2$–$3$ verbunden sind.