Ғаламның алыс бір түкпірінде жоғары дамыған $N$ ғаламшары бар галактика орналасқан. Ғаламшарлар 1-ден $N$-ге дейін нөмірленген. Әрбір ғаламшар бір ғарыш кемесін басқарады. Ғарыш кемесі не басқа ғаламшарға ұшу үшін пайдаланылып жатқан күйде, не пайдаланылмайтын күйде болады. $a$ ғаламшары басқаратын ғарыш кемесі $b$ ғаламшарына ұшу үшін пайдаланылып жатқан күйде болғанда, ғарыш кемесі $a$ ғаламшары мен $b$ ғаламшарының арасында көп рет әрі-бері қатынайды. Ғарыш кемесі $a$ ғаламшарынан $b$ ғаламшарына ұшқан кезде, қарапайым жолаушылар $a$ ғаламшарынан $b$ ғаламшарына жету үшін осы ғарыш кемесіне міне алады. Алайда ғарыш кемесі $b$ ғаламшарынан $a$ ғаламшарына қайтқан кезде, отын мәселесіне немесе жүк шектеулеріне байланысты қарапайым жолаушылар оған міне алмайды. Сондай-ақ, $a$ ғаламшары басқаратын ғарыш кемесі пайдаланылмайтын күйде болғанда, ол $a$ ғаламшарында күтіп тұрады.

Қазіргі уақытта барлық ғарыш кемелері пайдаланылмайтын күйде тұр. Болашақта ғарыш кемелерінің күйін өзгерту кестесі бекітілген. Күй өзгерістері келесі түрлерде болады:

• $a$ ғаламшары басқаратын (қазіргі уақытта пайдаланылмайтын күйде тұрған) ғарыш кемесін $b$ ғаламшарына ұшу үшін пайдаланылатын күйге ауыстыру. Бұл тек қарапайым жолаушылар ғарыш кемелеріне бірнеше рет міну арқылы $b$ ғаламшарынан $a$ ғаламшарына жете алмайтын жағдайда ғана орын алатынын ескеріңіз.
• $a$ ғаламшары басқаратын (қазіргі уақытта пайдаланылып жатқан күйде тұрған) ғарыш кемесін пайдаланылмайтын күйге ауыстыру.

Осы галактика арқылы саяхаттауды жоспарлаған екі адам кездесуді жоспарлау үшін келесі түрдегі бірнеше сұрақ дайындады:

• Кестенің белгілі бір сәтінде бір адам $a$ ғаламшарында, ал екіншісі $b$ ғаламшарында болсын делік. Екі адам қарапайым жолаушы ретінде ғарыш кемелерін пайдаланып кездесе ала ма? Сонымен қатар, егер олар кездесе алса, ғарыш кемесін пайдалану саны ең аз болуы үшін олар қай ғаламшарда кездесуі керек? Яғни, қарапайым жолаушылар ғарыш кемелеріне бірнеше рет міну арқылы $a$ ғаламшарынан $c$ ғаламшарына және $b$ ғаламшарынан $c$ ғаламшарына жете алатындай $c$ ғаламшары бар ма? Егер мұндай ғаламшар бар болса, $a$ ғаламшарынан $c$ ғаламшарына жету үшін ғарыш кемесін пайдалану саны мен $b$ ғаламшарынан $c$ ғаламшарына жету үшін ғарыш кемесін пайдалану санының қосындысын барынша азайтатын $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 \neq 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$ ғаламшарында болса, олар қарапайым жолаушы ретінде ғарыш кемелерін пайдаланып кездесе ала ма? Егер кездесе алса, ғарыш кемесін пайдалану санын барынша азайтатын $c$ ғаламшары қайсы? $1 \le A_i \le N$, $1 \le B_i \le N$, $A_i \neq 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 \neq 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

Ескертпе 1

Бұл мысалда күй өзгерістері мен сұрақтар келесі ретпен орын алады:

• 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