في مجرة بعيدة في أعماق الكون، يوجد $N$ جرمًا ذا حضارة متقدمة، مرقمة من $1$ إلى $N$. يدير كل جرم سفينة فضائية واحدة. تكون السفينة إما مستخدمة للسفر إلى جرم آخر، وإما غير مستخدمة. عندما تكون السفينة التي يديرها الجرم $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\le1\,000\,000$.
• $1\le Q\le1\,000\,000$.

المهام الفرعية

المهمة الفرعية 1 [10 نقاط]

تتحقق الشروط التالية.

• $N\le5\,000$.
• $Q\le5\,000$.

المهمة الفرعية 2 [30 نقطة]

• $T_i\ne2$ ($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