החווה של Farmer John מורכבת מקבוצה של $N$ שדות $(1 \leq N \leq 10^5)$, הממוספרים לנוחותנו $1 \ldots N$. בין השדות יש $M$ שבילים דו־כיווניים $(0 \leq M \leq 10^5)$, שכל אחד מהם מחבר זוג שדות.

בחווה יש שני אסמים, אחד בשדה $1$ והשני בשדה $N$. Farmer John רוצה להבטיח שאפשר ללכת בין שני האסמים לאורך סדרה של שבילים. הוא מוכן לבנות עד שני שבילים חדשים כדי להשיג מטרה זו. בשל מיקומם של השדות, עלות בניית שביל חדש בין השדות $i$ ו-$j$ היא $(i-j)^2$.

עזרו ל-Farmer John לקבוע את העלות המינימלית הדרושה כדי שיהיה אפשר להגיע מהאסם $1$ לאסם $N$ ולהפך.

קלט

כל מקרה בדיקה בקלט מכיל $T$ תתי־מקרים ($1\le T\le 20$), וצריך לפתור את כולם נכון כדי לעבור את מקרה הבדיקה בקלט.

השורה הראשונה בקלט מכילה את $T$, ולאחריה מופיעים $T$ תתי־מקרי בדיקה.

כל תת־מקרה בדיקה מתחיל בשני מספרים שלמים, $N$ ו-$M$. לאחר מכן מופיעות $M$ שורות, שכל אחת מהן מכילה שני מספרים שלמים $i$ ו-$j$, המציינים שביל בין שני שדות שונים $i$ ו-$j$. מובטח שבין כל שני שדות יש לכל היותר שביל אחד, ושסכום $N+M$ על פני כל תתי־מקרי הבדיקה אינו עולה על $5 \cdot 10^5$.

פלט

הדפיסו $T$ שורות. השורה ה-$i$ צריכה להכיל מספר שלם יחיד המציין את העלות המינימלית עבור תת־מקרה הבדיקה ה-$i$.

דוגמאות

קלט 1

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

פלט 1

2
1

הערה

בתת־מקרה הבדיקה הראשון, הפתרון האופטימלי הוא לחבר את השדות $2$ ו-$3$ באמצעות שביל, ואת השדות $3$ ו-$4$ באמצעות שביל נוסף.

בתת־מקרה הבדיקה השני, הפתרון האופטימלי הוא לחבר את השדות $3$ ו-$4$ באמצעות שביל. אין צורך בשביל שני.

תתי־משימות

• מקרה הבדיקה 2 מקיים $N \le 20$.
• מקרי הבדיקה 3-5 מקיימים $N \le 10^3$.
• למקרי הבדיקה 6-10 אין מגבלות נוספות.

מחבר הבעיה: Nick Wu