לפני כמה שנים הציע אותו מחבר את הבעיה הבאה לתחרות של תלמידי בית ספר: למחוק שני קודקודים סמוכים מגרף לא מכוון וקשיר נתון, שדרגתו המזערית לפחות $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$.