Beberapa tahun yang lalu, penulis yang sama mengajukan soal berikut untuk sebuah kompetisi sekolah: hapus dua simpul yang bertetangga dari sebuah graf tak berarah terhubung dengan derajat minimum setidaknya 2 sedemikian sehingga keterhubungannya tetap terjaga. Namun, soal itu terlalu mudah untuk kompetisi mahasiswa pada tahun 2020, jadi inilah soalnya.

Anda diberikan sebuah graf tak berarah terhubung dengan setidaknya 3 simpul, tanpa gelang maupun sisi ganda. Untuk setiap sisi, tentukan apakah menghapus kedua simpul ujungnya mempertahankan keterhubungan graf.

Perhatikan bahwa dalam soal ini, graf dapat mengandung simpul berderajat 1, tetapi tidak mengandung simpul berderajat 0 (karena graf terhubung dan memiliki setidaknya 3 simpul).

Masukan

Baris pertama masukan berisi dua bilangan bulat $n$ dan $m$ ($3 \le n \le 3 \cdot 10^5$; $n-1 \le m \le 3 \cdot 10^5$): berturut-turut jumlah simpul dan jumlah sisi. Baris ke-$i$ dari $m$ baris berikutnya berisi dua bilangan bulat $x$ dan $y$ yang dipisahkan oleh spasi: simpul-simpul ujung sisi ke-$i$ ($1 \le x,y \le n$; $x \ne y$). Dijamin bahwa graf terhubung dan tidak mengandung sisi ganda.

Keluaran

Keluarkan sebuah string biner sepanjang $m$: karakter ke-$i$ dari jawaban harus berupa “0” (tanpa tanda kutip) jika menghapus simpul-simpul ujung sisi ke-$i$ membuat graf tidak terhubung, dan “1” jika sebaliknya.

Contoh

Masukan 1

4 4
1 2
2 3
3 1
4 1

Keluaran 1

0101

Catatan

Perhatikan bahwa bukan hanya sisinya yang dihapus, melainkan juga kedua simpul ujungnya. Karena itu, tugas yang dimaksud berbeda dari mencari jembatan.

Sebagai contoh, pada contoh di atas, sisi $1$–$2$ bukanlah jembatan, tetapi menghapus simpul $1$ dan $2$ membuat graf tidak terhubung: graf yang dihasilkan terdiri atas dua simpul terisolasi $3$ dan $4$.

Sebaliknya, sisi $1$–$4$ adalah jembatan, tetapi menghapus simpul $1$ dan $4$ membuat graf terhubung: graf yang dihasilkan terdiri atas dua simpul $2$ dan $3$, yang dihubungkan oleh sisi $2$–$3$.