트리오

윤이, 달구, 포닉스는 2025 UDPC를 기다리며 나무 한 그루를 함께 기르고 있다. 이 나무는 $N$개의 정점으로 이루어진 루트 없는 트리로 표현되며, 트리의 정점은 $1$번부터 $N$번까지의 번호로 구분된다.

세 친구는 나무에 대한 취향이 뚜렷해서 각 정점에 자신만의 새로운 번호를 붙였다. 구체적으로는, 기존의 $i$번 정점에 윤이는 번호 $A_i$를, 달구는 $B_i$를, 포닉스는 $C_i$를 붙였다. UDPC가 끝난 후 각자의 집으로 돌아가야 하는 세 친구는 이 나무를 세 부분으로 나누기로 했다. 이는 서로 다른 두 개의 간선을 골라 없애는 것을 의미한다.

이때, 쪼개진 각 부분 트리는 아래와 같은 조건을 만족해야 한다.

• 한 부분 트리에 속한 원래 정점의 번호를 $\{v_1,v_2,\cdots ,v_m\}$이라 하면, $\{A_{v_1},\cdots A_{v_m}\} =\{B_{v_1},\cdots B_{v_m}\} =\{C_{v_1},\cdots C_{v_m}\}$ 이어야 한다.
• 즉, 모든 부분 트리에 대해서 각 친구가 새로 붙인 번호의 집합이 같아야 한다.

세 친구는 나눠진 세 부분 트리 중 가장 크기가 작은 것의 크기를 최대한 크게 하고 싶다. 트리의 크기는 포함된 정점의 개수로 정의된다.

세 친구를 위해 나무를 공평하게 나누어 보자.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. $(1\le T\le 100\, 000)$

각 테스트 케이스의 첫째 줄에 정점의 개수 $N$이 주어진다. $(3\le N\le 300\,000)$

각 테스트 케이스의 둘째 줄에 윤이가 새로 붙인 정점 번호 $A_1,\cdots ,A_N$이 공백으로 구분되어 주어진다.

각 테스트 케이스의 셋째 줄에 달구가 새로 붙인 정점 번호 $B_1,\cdots ,B_N$이 공백으로 구분되어 주어진다.

각 테스트 케이스의 넷째 줄에 포닉스가 새로 붙인 정점 번호 $C_1,\cdots ,C_N$이 공백으로 구분되어 주어진다.

$A$, $B$, $C$는 모두 길이가 $N$인 순열임이 보장된다.

각 테스트 케이스의 다섯 번째 줄부터 $N-1$개의 줄에 걸쳐 트리의 간선을 이루는 서로 다른 두 정점 $u$, $v$가 주어진다. $(1\le u,v\le N)$

주어지는 간선이 트리 구조를 이룸과, 모든 테스트 케이스에 대해 $N$의 합이 $300\,000$ 이하임이 보장된다.

각 테스트 케이스에 대해, 나무를 세 부분으로 나눌 때 가장 작은 부분 트리 크기의 최댓값을 한 줄에 하나씩 순서대로 출력하여라. 만약 나무를 세 부분으로 나누는 것이 불가능하다면 $-1$을 출력하여라.