트리오

시간 제한3초메모리 제한1024 MB

요약
간선 두 개를 지워 트리를 세 부분으로 나눌 때, 각 부분에서 A, B, C 번호 집합이 모두 같아야 하며 가장 작은 부분의 크기를 최대로 하는 값을 구한다.
난이도

어려움10점 중 8점

유형
트리, 해시맵, DFS, 그리디
정답자
아직 제출이 없습니다

문제

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

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

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

  • 한 부분 트리에 속한 원래 정점의 번호를 v_1,v_2,⋯ ,v_m\\{v\_1,v\_2,\cdots ,v\_m\\}이라 하면, A_v_1,⋯A_v_m=B_v_1,⋯B_v_m=C_v_1,⋯C_v_m\\{A\_{v\_1},\cdots A\_{v\_m}\\} =\\{B\_{v\_1},\cdots B\_{v\_m}\\} =\\{C\_{v\_1},\cdots C\_{v\_m}\\} 이어야 한다.
  • 즉, 모든 부분 트리에 대해서 각 친구가 새로 붙인 번호의 집합이 같아야 한다.

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

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

입력

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

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

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

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

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

AA, BB, CC는 모두 길이가 NN인 순열임이 보장된다.

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

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

출력

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

예제1

  1. 예제 1

    입력
    3
5
1 2 3 4 5
3 2 1 4 5
1 4 3 2 5
1 2
1 3
2 4
2 5
3
1 2 3
2 3 1
3 1 2
1 2
1 3
10
1 2 3 4 5 6 7 8 9 10
1 2 6 8 7 3 5 4 9 10
2 1 9 4 5 6 10 8 3 7
1 2
1 3
2 7
2 8
8 4
7 5
10 7
6 3
3 9
    예상 출력
    1
-1
3