Сізге әрқайсысында $N$ төбесі бар $A$ және $B$ екі ағашы берілген. Екі ағаштың да нөмірленген төбелер жиыны бірдей: $\{1, 2, \dots, N\}$.

Әрбір $i$ ($1 \le i \le N - 1$) үшін $A$ ағашының $i$-ші қабырғасы $u_i$ және $v_i$ төбелерін қосады. Әрбір $j$ ($1 \le j \le N - 1$) үшін $B$ ағашының $j$-ші қабырғасы $x_j$ және $y_j$ төбелерін қосады.

Әрбір $i = 1, 2, \dots, N - 1$ үшін келесі есепті шығарыңыз.

• Келесі алмастырудан кейін $A$ да, $B$ да ағаш болып қалатындай $1 \le j \le N - 1$ шартын қанағаттандыратын бүтін $j$ санын табыңыз:
  • $A$ ағашынан $u_i$ мен $v_i$ төбелерін қосатын қабырғаны өшіріп, $B$ ағашынан $x_j$ мен $y_j$ төбелерін қосатын қабырғаны өшіріңіз.
  • Содан кейін $A$ ағашына $x_j$ мен $y_j$ төбелерін қосатын қабырғаны қосып, $B$ ағашына $u_i$ мен $v_i$ төбелерін қосатын қабырғаны қосыңыз.

Әрбір алмастыру бастапқы $A$ және $B$ ағаштарынан бастап тәуелсіз түрде қарастырылады.

Берілген шектеулерде әрбір $i$ үшін осындай кемінде бір бүтін $j$ саны табылатынын дәлелдеуге болады.

Input

Кіріс деректері келесі форматтағы бір тест жағдайынан тұрады.

$$ \begin{aligned} &N \\ &u_1 \ v_1 \\ &u_2 \ v_2 \\ &\vdots \\ &u_{N-1} \ v_{N-1} \\ &x_1 \ y_1 \\ &x_2 \ y_2 \\ &\vdots \\ &x_{N-1} \ y_{N-1} \end{aligned} $$

Бүтін $N$ саны — $A$ және $B$ ағаштарының төбелер саны ($2 \le N \le 2 \times 10^5$).

Келесі $N - 1$ жол $A$ ағашының қабырғаларын сипаттайды. Әрбір $i = 1, \dots, N - 1$ үшін бүтін $u_i$ және $v_i$ ($1 \le u_i, v_i \le N$) сандары $i$-ші қабырға $u_i$ мен $v_i$ төбелерін қосатынын білдіреді. $A$ ағаш екеніне кепілдік беріледі.

Келесі $N - 1$ жол $B$ ағашының қабырғаларын сипаттайды. Әрбір $j = 1, \dots, N - 1$ үшін бүтін $x_j$ және $y_j$ ($1 \le x_j, y_j \le N$) сандары $j$-ші қабырға $x_j$ мен $y_j$ төбелерін қосатынын білдіреді. $B$ ағаш екеніне кепілдік беріледі.

Output

$N - 1$ жол шығарыңыз. Әрбір $i = 1, 2, \dots, N - 1$ үшін $i$-ші жолда $A$ ағашының $i$-ші қабырғасы үшін есеп шартын қанағаттандыратын бүтін $j$ саны болуы керек.

Егер мүмкін жауаптар бірнешеу болса, олардың кез келгенін шығаруға болады.

Examples

Input 1

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

Output 1

1
3
2

Note

Мысалдағы шығыстың бірінші жолында $i = 1$ үшін $j = 1$ таңдалған. $A$ ағашының $(1, 3)$ қабырғасын $B$ ағашының $(1, 2)$ қабырғасымен алмастыру $A$ мен $B$ екеуін де ағаш күйінде қалдырады.

$i = 2$ үшін $A$ ағашының қабырғасы да, $B$ ағашының таңдалған қабырғасы да $(2, 4)$ болып табылады, сондықтан оларды алмастыру ешбір ағашты өзгертпейді. Басқа да дұрыс жауаптар болуы мүмкін.