หลายปีก่อน ผู้แต่งคนเดียวกันนี้เคยเสนอปัญหาต่อไปนี้ในการแข่งขันระดับโรงเรียน: ลบจุดยอดสองจุดที่อยู่ติดกันออกจากกราฟไม่มีทิศทางที่เชื่อมต่อกันและมีดีกรีต่ำสุดอย่างน้อย $2$ โดยให้กราฟยังคงเชื่อมต่อกัน แต่ปัญหานั้นง่ายเกินไปสำหรับการแข่งขันนักศึกษาในปี 2020 เราจึงมีปัญหานี้มาให้

กำหนดกราฟไม่มีทิศทางที่เชื่อมต่อกัน มีจุดยอดอย่างน้อย $3$ จุด และไม่มีวงวนที่จุดยอดเดียวหรือเส้นเชื่อมซ้ำ สำหรับแต่ละเส้นเชื่อม จงพิจารณาว่าการลบจุดปลายทั้งสองของเส้นเชื่อมนั้นยังคงทำให้กราฟเชื่อมต่อกันหรือไม่

สังเกตว่าในปัญหานี้ กราฟอาจมีจุดยอดที่มีดีกรี $1$ แต่ไม่มีจุดยอดที่มีดีกรี $0$ (เนื่องจากกราฟเชื่อมต่อกันและมีจุดยอดอย่างน้อย $3$ จุด)

ข้อมูลนำเข้า

บรรทัดแรกของข้อมูลนำเข้ามีจำนวนเต็มสองจำนวน $n$ และ $m$ ($3 \le n \le 3 \cdot 10^5$; $n-1 \le m \le 3 \cdot 10^5$) ซึ่งเป็นจำนวนจุดยอดและจำนวนเส้นเชื่อมตามลำดับ บรรทัดที่ $i$ ใน $m$ บรรทัดถัดไปมีจำนวนเต็มสองจำนวน $x$ และ $y$ คั่นด้วยช่องว่าง ซึ่งเป็นจุดปลายของเส้นเชื่อมที่ $i$ ($1 \le x,y \le n$; $x \ne y$) รับประกันว่ากราฟเชื่อมต่อกันและไม่มีเส้นเชื่อมซ้ำ

ข้อมูลส่งออก

พิมพ์สตริงฐานสองหนึ่งสตริงที่มีความยาว $m$: อักขระที่ $i$ ของคำตอบต้องเป็น “0” (ไม่รวมเครื่องหมายคำพูด) หากการลบจุดปลายของเส้นเชื่อมที่ $i$ ทำให้กราฟไม่เชื่อมต่อกัน และเป็น “1” ในกรณีอื่น

ตัวอย่าง

ข้อมูลนำเข้า 1

4 4
1 2
2 3
3 1
4 1

ข้อมูลส่งออก 1

0101

หมายเหตุ

โปรดสังเกตว่าไม่ได้ลบเพียงเส้นเชื่อมเท่านั้น แต่ลบจุดปลายทั้งสองด้วย ดังนั้นงานในปัญหานี้จึงแตกต่างจากการหาเส้นเชื่อมสะพาน

ตัวอย่างเช่น ในตัวอย่าง เส้นเชื่อม $1$–$2$ ไม่ใช่สะพาน แต่การลบจุดยอด $1$ และ $2$ ทำให้กราฟไม่เชื่อมต่อกัน โดยกราฟที่เหลือประกอบด้วยจุดยอดโดดเดี่ยวสองจุด คือ $3$ และ $4$

ในทางกลับกัน เส้นเชื่อม $1$–$4$ เป็นสะพาน แต่การลบจุดยอด $1$ และ $4$ ทำให้กราฟยังคงเชื่อมต่อกัน โดยกราฟที่เหลือประกอบด้วยจุดยอดสองจุด คือ $2$ และ $3$ ซึ่งเชื่อมกันด้วยเส้นเชื่อม $2$–$3$