قبل عدة سنوات، اقترح المؤلف نفسه المسألة الآتية لمسابقة مدرسية: احذف رأسين متجاورين من رسم بياني معطى متصل وغير موجه، درجة كل رأس فيه لا تقل عن $2$، بطريقة تحافظ على اتصاله. لكن تلك المسألة بسيطة جدًا بالنسبة إلى مسابقة طلابية في عام 2020، لذا ها نحن ذا.

أُعطيت رسمًا بيانيًا متصلاً غير موجه، له ثلاثة رؤوس على الأقل، ولا يحتوي على حلقات ذاتية أو حواف متعددة. لكل حافة، حدد ما إذا كان حذف كلا طرفيها يحافظ على اتصال الرسم البياني.

لاحظ أن الرسم البياني في هذه المسألة قد يحتوي على رؤوس درجتها $1$، لكنه لا يحتوي على رؤوس درجتها $0$ (لأنه متصل وله ثلاثة رؤوس على الأقل).

الإدخال

يحتوي السطر الأول من الإدخال على عددين صحيحين $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$.