נתון לכם גרף לא מכוון ללא לולאות עצמיות או קשתות מרובות.

הקצו ערך שלם אי-שלילי לכל קודקוד בגרף. השמה נקראת תקפה אם היא מקיימת שני תנאים:

• לכל שני קודקודים שכנים יש ערכים הנבדלים זה מזה ב-$1$ בדיוק;
• אם הערך של קודקוד קטן ממש מהערכים של כל שכניו, אז הוא שווה ל-$0$.

מצאו את מספר ההשמות התקפות מודולו $998\,244\,353$. שתי השמות נחשבות שונות אם קיים קודקוד שיש לו ערכים שונים בהשמות אלו.

קלט

השורה הראשונה מכילה מספר שלם $t$, מספר מקרי הבדיקה.

השורה הראשונה של כל מקרה בדיקה מכילה שני מספרים שלמים $n$ ו-$m$ ($2 \le n \le 10^6$, $1 \le m \le 10^6$): מספר הקודקודים והקשתות בגרף.

כל אחת מ-$m$ השורות הבאות מכילה שני מספרים שלמים $u$ ו-$v$ ($1 \le u, v \le n$, $u \ne v$): נקודות הקצה של הקשת המתאימה. הגרף אינו מכיל לולאות עצמיות או קשתות מרובות. לכל קודקוד יש לפחות שכן אחד.

סכום ערכי ה-$m$ על פני כל מקרי הבדיקה אינו עולה על $10^6$.

פלט

עבור כל מקרה בדיקה, הדפיסו מספר שלם אחד: מספר ההשמות התקפות מודולו $998\,244\,353$.

דוגמה

קלט 1

2
4 3
1 2
2 3
3 4
3 3
1 2
2 3
1 3

פלט 1

6
0