Il y a plusieurs années, le même auteur avait proposé le problème suivant pour un concours scolaire : supprimer deux sommets adjacents d'un graphe non orienté connexe donné, de degré minimal au moins égal à $2$, de façon à préserver sa connexité. Mais ce problème est trop simple pour un concours étudiant en 2020, alors allons-y.

On vous donne un graphe non orienté connexe comportant au moins $3$ sommets, sans boucles ni arêtes multiples. Pour chaque arête, déterminez si la suppression de ses deux extrémités préserve la connexité du graphe.

Remarquez que, dans ce problème, le graphe peut contenir des sommets de degré $1$, mais aucun sommet de degré $0$ (puisqu'il est connexe et possède au moins $3$ sommets).

Entrée

La première ligne de l'entrée contient deux entiers $n$ et $m$ ($3 \le n \le 3 \cdot 10^5$ ; $n - 1 \le m \le 3 \cdot 10^5$), respectivement le nombre de sommets et le nombre d'arêtes. La $i$-ième des $m$ lignes suivantes contient deux entiers $x$ et $y$ séparés par un espace : les extrémités de la $i$-ième arête ($1 \le x, y \le n$ ; $x \ne y$). Il est garanti que le graphe est connexe et ne contient pas d'arêtes multiples.

Sortie

Affichez une seule chaîne binaire de longueur $m$ : le $i$-ième caractère de la réponse doit être « 0 » (sans guillemets) si la suppression des extrémités de la $i$-ième arête rend le graphe non connexe, et « 1 » sinon.

Exemples

Entrée 1

4 4
1 2
2 3
3 1
4 1

Sortie 1

0101

Remarque

Remarquez que l'on supprime non seulement l'arête elle-même, mais aussi ses deux extrémités. Cette tâche est donc différente de la recherche de ponts.

Par exemple, dans l'exemple, l'arête $1$–$2$ n'est pas un pont, mais supprimer les sommets $1$ et $2$ rend le graphe non connexe : le graphe obtenu est constitué des deux sommets isolés $3$ et $4$.

En revanche, l'arête $1$–$4$ est un pont, mais supprimer les sommets $1$ et $4$ laisse le graphe connexe : le graphe obtenu est constitué des deux sommets $2$ et $3$, reliés par l'arête $2$–$3$.