Vài năm trước, chính tác giả này đã đề xuất bài toán sau cho một cuộc thi học sinh: xóa hai đỉnh kề nhau khỏi một đồ thị vô hướng liên thông cho trước có bậc nhỏ nhất ít nhất là $2$, sao cho vẫn giữ được tính liên thông. Nhưng bài toán đó quá đơn giản đối với một cuộc thi sinh viên năm 2020, vì vậy chúng ta có bài toán này.

Cho một đồ thị vô hướng liên thông có ít nhất $3$ đỉnh, không có khuyên và cạnh song song. Với mỗi cạnh, hãy xác định xem việc xóa cả hai đầu mút của nó có giữ được tính liên thông của đồ thị hay không.

Lưu ý rằng trong bài toán này, đồ thị có thể chứa các đỉnh bậc $1$, nhưng không có đỉnh bậc $0$ (vì đồ thị liên thông và có ít nhất $3$ đỉnh).

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa hai số nguyên $n$ và $m$ ($3 \le n \le 3 \cdot 10^5$; $n-1 \le m \le 3 \cdot 10^5$): lần lượt là số đỉnh và số cạnh. Dòng thứ $i$ trong $m$ dòng tiếp theo chứa hai số nguyên $x$ và $y$ cách nhau bởi dấu cách: hai đầu mút của cạnh thứ $i$ ($1 \le x,y \le n$; $x \ne y$). Đảm bảo đồ thị liên thông và không chứa cạnh song song.

Dữ liệu ra

In một xâu nhị phân duy nhất có độ dài $m$: ký tự thứ $i$ của câu trả lời phải là 0 (không có dấu ngoặc kép) nếu xóa hai đầu mút của cạnh thứ $i$ làm đồ thị mất liên thông, và là 1 trong trường hợp ngược lại.

Ví dụ

Dữ liệu vào 1

4 4
1 2
2 3
3 1
4 1

Dữ liệu ra 1

0101

Ghi chú

Lưu ý rằng không chỉ bản thân cạnh bị xóa, mà cả hai đầu mút của nó cũng bị xóa. Vì thế, bài toán này khác với việc tìm các cầu.

Chẳng hạn, trong ví dụ, cạnh $1$–$2$ không phải là cầu, nhưng xóa các đỉnh $1$ và $2$ khiến đồ thị mất liên thông: đồ thị thu được gồm hai đỉnh cô lập $3$ và $4$.

Mặt khác, cạnh $1$–$4$ là cầu, nhưng xóa các đỉnh $1$ và $4$ lại khiến đồ thị liên thông: đồ thị thu được gồm hai đỉnh $2$ và $3$, nối với nhau bởi cạnh $2$–$3$.