각각 $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$가 적어도 하나 존재함을 증명할 수 있습니다.

입력

입력은 다음 형식의 단일 테스트 케이스로 이루어져 있습니다.

$$ \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$가 트리임이 보장됩니다.

출력

$N - 1$개의 줄을 출력합니다. 각 $i = 1, 2, \dots, N - 1$에 대하여, $i$번째 줄에는 $A$의 $i$번째 간선에 대해 문제의 조건을 만족하는 정수 $j$를 출력해야 합니다.

가능한 답이 여러 개인 경우, 그중 아무것이나 출력해도 됩니다.

예제

입력 1

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

출력 1

1
3
2

참고

예제 출력의 첫 번째 줄에서는 $i = 1$에 대해 $j = 1$이 선택되었습니다. $A$의 간선 $(1, 3)$과 $B$의 간선 $(1, 2)$를 교환하면 $A$와 $B$ 모두 트리로 남습니다.

$i = 2$의 경우, $A$의 간선과 선택된 $B$의 간선이 모두 $(2, 4)$이므로 이를 교환해도 두 트리 모두 변하지 않습니다. 다른 올바른 출력도 가능합니다.