두 정점 삭제 다시

몇 년 전 같은 저자가 학교 대회에 다음 문제를 냈다. 최소 차수가 $2$ 이상인 연결된 무방향 그래프에서 인접한 두 정점을 삭제하되, 연결성은 유지하는 문제였다. 그 문제는 2020년 학생 대회에는 너무 쉬워서, 이번에는 더 어려운 문제를 준비했다.

정점이 $3$개 이상인 연결된 무방향 그래프가 주어진다. 자기 루프와 다중 간선은 없다. 각 간선에 대해, 그 간선의 두 끝점을 모두 삭제했을 때 그래프가 연결된 상태를 유지하는지 판단하라.

그래프는 차수가 $1$인 정점을 포함할 수 있다. 하지만 연결되어 있고 정점이 $3$개 이상이므로 차수가 $0$인 정점은 없다.

첫 줄에 정점 수 $n$과 간선 수 $m$이 주어진다 ($3 \leq n \leq 3 \cdot 10^5$, $n - 1 \leq m \leq 3 \cdot 10^5$). 이어지는 $m$개의 줄에서 $i$번째 줄에는 $i$번째 간선의 두 끝점 $x$와 $y$가 공백으로 구분되어 주어진다 ($1 \leq x, y \leq n$, $x \neq y$). 그래프는 연결되어 있고 다중 간선이 없다.

길이가 $m$인 이진 문자열을 출력한다. $i$번째 문자는 $i$번째 간선의 두 끝점을 삭제했을 때 그래프가 끊어지면 "0", 그렇지 않으면 "1"이다.

간선만 지워지는 것이 아니라 두 끝점이 모두 삭제된다는 점에 주의하라. 따라서 이 문제는 다리(bridge)를 찾는 문제와 다르다.

예를 들어 예제에서 간선 $1$-$2$는 다리가 아니다. 하지만 정점 $1$과 $2$를 삭제하면 그래프가 끊어진다. 남은 정점은 고립된 $3$과 $4$뿐이기 때문이다. 반대로 간선 $1$-$4$는 다리이지만, 정점 $1$과 $4$를 삭제하면 그래프는 연결된 상태를 유지한다. 남은 정점 $2$와 $3$이 간선 $2$-$3$으로 이어져 있기 때문이다.