בגלקסיה מרוחקת מאוד יש $N$ כוכבים בעלי תרבויות מתקדמות, שמספריהם מ־$1$ עד $N$. כל כוכב מנהל חללית אחת. חללית נמצאת באחד משני מצבים: בשימוש לצורך נסיעה לכוכב אחר, או שאינה בשימוש. כאשר החללית שמנהל כוכב $a$ נמצאת בשימוש לצורך נסיעה לכוכב $b$, היא נוסעת הלוך ושוב בין $a$ ל־$b$ פעמים רבות. כשהיא נוסעת מ־$a$ ל־$b$, נוסעים רגילים יכולים לעלות עליה ולנסוע מ־$a$ ל־$b$. אולם כשהיא חוזרת מ־$b$ ל־$a$, נוסעים רגילים אינם יכולים לעלות עליה, מסיבות כגון מגבלות דלק והובלת מטען. כאשר החללית שמנהל כוכב $a$ אינה בשימוש, היא ממתינה בכוכב $a$.

כעת כל החלליות אינן בשימוש. לוח הזמנים של השינויים העתידיים במצבי החלליות כבר נקבע. כל שינוי הוא מאחד הסוגים הבאים.

• להעביר את החללית שאינה בשימוש ומנוהלת בידי כוכב $a$ למצב של שימוש לצורך נסיעה לכוכב $b$. הדבר נעשה רק כאשר נוסע רגיל אינו יכול להגיע מ־$b$ ל־$a$ באמצעות נסיעות בחלליות.
• להעביר חללית שנמצאת בשימוש ומנוהלת בידי כוכב $a$ למצב שבו אינה בשימוש.

שני אנשים המתכננים לטייל בגלקסיה זו הכינו כמה שאלות מהסוג הבא כדי לתכנן היכן להיפגש.

• אם ברגע מסוים בלוח הזמנים אחד נמצא בכוכב $a$ והשני בכוכב $b$, האם הם יכולים להיפגש באמצעות חלליות כנוסעים רגילים? ואם כן, באיזה כוכב עליהם להיפגש כדי למזער את מספר הנסיעות בחלליות? כלומר, האם קיים כוכב $c$ שאליו נוסע רגיל יכול להגיע באמצעות נסיעות בחלליות גם מ־$a$ וגם מ־$b$? ואם קיים, איזה כוכב $c$ ממזער את סכום מספר הנסיעות בחלליות מ־$a$ ל־$c$ ומספר הנסיעות בחלליות מ־$b$ ל־$c$?

בתור מתכנת מצטיין, התבקשת למצוא תשובות לכל השאלות של השניים.

המשימה

כתוב תוכנית העונה על השאלות, בהינתן לוח הזמנים של השינויים במצבי החלליות והשאלות בסדר כרונולוגי.

קלט

קרא מהקלט הסטנדרטי את הנתונים הבאים.

• השורה הראשונה מכילה את המספרים השלמים $N,Q$, מופרדים ברווח. הם מציינים שמספר הכוכבים הוא $N$, ושהסכום של מספר השינויים במצבים ומספר השאלות הוא $Q$.
• $Q$ השורות הבאות מתארות את השינויים במצבים ואת השאלות בסדר כרונולוגי. השורה ה־$i$ ($1 \le i \le Q$) מכילה שניים או שלושה מספרים שלמים המופרדים ברווחים. אם המספר הראשון הוא $T_i$, מתקיים אחד המקרים הבאים.

מקרה (i): $T_i=1$

השורה מכילה את המספרים השלמים $T_i,A_i,B_i$ ומייצגת את שינוי המצב הבא: להעביר את החללית שמנהל כוכב $A_i$ למצב של שימוש לצורך נסיעה לכוכב $B_i$.

מובטח כי $1 \le A_i \le N$, $1 \le B_i \le N$ ו־$A_i \ne B_i$; כי באותו רגע החללית שמנהל כוכב $A_i$ אינה בשימוש; וכי באותו רגע נוסע רגיל אינו יכול להגיע מכוכב $B_i$ לכוכב $A_i$ באמצעות נסיעות בחלליות.

מקרה (ii): $T_i=2$

השורה מכילה את המספרים השלמים $T_i,A_i$ ומייצגת את שינוי המצב הבא: להעביר את החללית שמנהל כוכב $A_i$ למצב שבו אינה בשימוש.

מובטח כי $1 \le A_i \le N$ וכי באותו רגע החללית שמנהל כוכב $A_i$ נמצאת בשימוש.

מקרה (iii): $T_i=3$

השורה מכילה את המספרים השלמים $T_i,A_i,B_i$ ומייצגת את השאלה הבאה: אם באותו רגע אחד נמצא בכוכב $A_i$ והשני בכוכב $B_i$, האם הם יכולים להיפגש באמצעות חלליות כנוסעים רגילים? ואם כן, באיזה כוכב עליהם להיפגש כדי למזער את מספר הנסיעות בחלליות?

מובטח כי $1 \le A_i \le N$, $1 \le B_i \le N$ ו־$A_i \ne B_i$.

פלט

לכל שאלה, הדפס לפלט הסטנדרטי, לפי הסדר ובשורה נפרדת:

• אם הם יכולים להיפגש, את מספר הכוכב שבו עליהם להיפגש כדי למזער את מספר הנסיעות בחלליות.
• אם הם אינם יכולים להיפגש, את המספר השלם $-1$.

מגבלות

כל נתוני הקלט מקיימים את התנאים הבאים.

• $2 \le N \le 1\,000\,000$.
• $1 \le Q \le 1\,000\,000$.

תתי־משימות

תת־משימה 1 [10 נקודות]

מתקיימים התנאים הבאים.

• $N \le 5\,000$.
• $Q \le 5\,000$.

תת־משימה 2 [30 נקודות]

• מתקיים $T_i \ne 2$ ($1 \le i \le Q$).

תת־משימה 3 [60 נקודות]

אין מגבלות נוספות.

דוגמאות

קלט 1

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

פלט 1

-1
4

הערה

בדוגמה זו, השינויים במצבים והשאלות הם כדלקמן, לפי הסדר.

• החללית שמנהל כוכב 2 עוברת למצב של שימוש לצורך נסיעה לכוכב 4.
• אם באותו רגע שני האנשים נמצאים בכוכבים 2 ו־6, הם אינם יכולים להיפגש, ולכן מודפס $-1$.
• החללית שמנהל כוכב 4 עוברת למצב של שימוש לצורך נסיעה לכוכב 3.
• החללית שמנהל כוכב 6 עוברת למצב של שימוש לצורך נסיעה לכוכב 4.
• אם באותו רגע שני האנשים נמצאים בכוכבים 2 ו־6, הם יכולים להיפגש בכוכב 3 או בכוכב 4. כדי למזער את מספר הנסיעות בחלליות עליהם להיפגש בכוכב 4, ולכן מודפס 4.

קלט 2

8 36
1 1 2
1 6 5
1 7 8
3 5 6
1 5 4
1 8 1
3 7 2
3 3 8
3 1 8
1 3 2
1 4 1
3 8 5
3 4 3
2 4
3 6 8
1 2 5
3 6 8
2 8
3 1 4
3 6 8
3 6 3
2 3
3 1 2
1 4 3
3 2 6
1 8 3
3 1 7
3 1 6
3 5 4
2 2
2 5
1 3 6
1 2 7
3 1 4
3 1 5
3 6 7

פלט 2

5
2
-1
1
1
2
-1
5
4
-1
5
2
5
3
5
4
3
5
6