ל-Bobo יש גרף לא מכוון וקשיר $G$ בעל $n$ קודקודים ו-$m$ קשתות, שקודקודיו מסומנים לנוחות במספרים $1,2,\ldots,n$.

Bobo בוחר תת-קבוצה לא ריקה של קשתות, כך שהגרף עם הקשתות שנבחרו עדיין קשיר. הוא רוצה לדעת את מספר תתי-הקבוצות האלה מודולו $2$.

שימו לב שגרף הוא קשיר אם לכל שני קודקודים $a$ ו-$b$ קיים מסלול המחבר את $a$ ואת $b$.

קלט

הקלט מכיל אפס מקרי בדיקה או יותר, ומסתיים בסוף הקובץ. עבור כל מקרה בדיקה:

השורה הראשונה מכילה שני מספרים שלמים $n$ ו-$m$ ($2 \le n \le 2 \cdot 10^5$, $1 \le m \le 2 \cdot 10^5$).

השורה ה-$i$ מבין $m$ השורות הבאות מכילה שני מספרים שלמים $a_i$ ו-$b_i$, המציינים קשת בין הקודקודים $a_i$ ו-$b_i$.

מובטח שסכום כל ערכי $m$ אינו עולה על $2 \cdot 10^5$, ושכל הגרפים הנתונים קשירים.

פלט

עבור כל מקרה בדיקה, הדפיסו מספר שלם המציין את השארית מודולו $2$.

דוגמאות

קלט 1

2 1
1 2
3 2
1 2
2 3
3 3
1 2
2 3
3 1

פלט 1

1
1
0