Алиса мен Бобта $1$-ден $2N$-ге дейін нөмірленген $2N$ төбеден тұратын $T$ ағашы бар.

Бобта $K$ бүтін саны бар және ол $1$-ден $2N$-ге дейінгі әрбір бүтін сан дәл бір жұпта кездесетіндей және арақашықтықтар қосындысы $\sum_{i=1}^N \text{dist}(X_i, Y_i) = K$ болатындай $N$ жұпты $(X_1, Y_1), (X_2, Y_2), \dots, (X_N, Y_N)$ тапқысы келеді, мұндағы $\text{dist}(X_i, Y_i)$ — ағаштағы $X_i$ мен $Y_i$ төбелерінің арасындағы арақашықтық, яғни $X_i$ мен $Y_i$ арасындағы (жалғыз) жолдағы қырлар саны.

Алиса Бобтың мақсатына жеткенін қаламайды. Ол келесі амалды орындай алады:

• $T$ ағашынан $(U, V)$ қырын өшіру.
• $T$ ағаш болып қалатындай жаңа $(A, B)$ қырын қосу.

Өшіру және қосу үшін бірдей қырды таңдауға рұқсат етілетінін ескеріңіз, бұл бастапқы ағашты өзгеріссіз қалдырады.

Алисаға өшірілуі тиіс $(U, V)$ қырын және қосылуы тиіс $(A, B)$ қырын табуға көмектесіңіз. Егер бірнеше шешім болса, кез келгенін табуға болады.

Осы есептің шектеулерінде әрқашан бір қырды өшіріп, бір қырды қосу арқылы $1$-ден $2N$-ге дейінгі әрбір бүтін сан дәл бір жұпта кездесетін және арақашықтықтар қосындысы $K$-ға тең болатын $N$ жұп $(X_1, Y_1), (X_2, Y_2), \dots, (X_N, Y_N)$ табылмайтындай етуге болатынын дәлелдеуге болады.

Кіріс деректер

Кіріс деректер келесі форматта беріледі:

$$T$$ $$N\ K$$ $$U_1\ V_1$$ $$U_2\ V_2$$ $$\vdots$$ $$U_{{2N-1}}\ V_{{2N-1}}$$ $$\vdots$$

• Барлық кіріс мәндері бүтін сандар.
• $1 \le T \le 10^4$
• $2 \le N \le 2 \times 10^5$
• $1 \le K \le 10^{12}$
• $1 \le U_i, V_i \le 2N$
• Берілген қырлар ағаш құрайтынына кепілдік беріледі.
• Барлық тест жағдайлары бойынша $N$ мәндерінің қосындысы $2 \times 10^5$-нен аспайтынына кепілдік беріледі.

Шығыс деректер

Әрбір тест жағдайы үшін екі жол шығарыңыз:

Бірінші жолда екі бүтін сан $U$ және $V$ болуы керек — бұл $(U, V)$ қыры өшірілетінін білдіреді.

Екінші жолда екі бүтін сан $A$ және $B$ болуы керек — бұл $(A, B)$ қыры қосылатынын білдіреді.

Егер бірнеше шешім болса, кез келгенін шығарыңыз.

Мысал

Кіріс деректер 1

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

Шығыс деректер 1

1 2
1 2
1 2
1 3

Ескертпе

1-тест жағдайы: Бастапқы ағашта Бобтың $K = 20$ ұпайын алу мүмкіндігі онсыз да жоқ, сондықтан Алиса кез келген бар қырды өшіріп, қайта қоса салады.

2-тест жағдайы: Бастапқы ағашта Бобтың $K = 4$ ұпайын алу мүмкіндігі бар, мысалы $(1, 4)$ және $(2, 3)$ жұптарын таңдау арқылы. Алиса $(1, 2)$ қырын өшіріп, $(1, 3)$ қырын қосады. Осы жаңа ағашта Боб $4$ ұпайын ала алмайды.