시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 102 38 11 20.000%

문제

D-균형 트리는 다음 세 조건을 만족하는 트리이다.

  • 트리의 각 정점은 검정색 또는 흰색이다.
  • 각 검정색 정점에서 거리가 최대 D인 다른 검정색 정점이 존재한다.
  • 각 흰색 정점에서 거리가 최대 D인 다른 흰색 정점이 존재한다.

트리의 정보와 정점의 색이 주어졌을 때, 만족하는 D의 값 중에서 최솟값을 구해보자.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 이루어져 있다.

  • 첫째 줄에 정점의 수 N이 주어진다.
  • 둘째 줄부터 N-1개의 줄에 두 정수 x, y가 주어진다. 정점 x와 y를 연결하는 간선을 의미한다.
  • 마지막 줄에 정점의 색이 1번 정점부터 N번 정점까지 순서대로 주어진다. 0은 흰색, 1은 검정색을 의미한다.

출력

각 테스트 케이스마다 만족하는 D의 값 중에서 최솟값을 한 줄에 하나씩 출력한다. 가능한 D의 값이 존재하지 않으면 -1을 출력한다.

제한

  • 3 ≤ N ≤ 500,000
  • N의 합은 500,000보다 작거나 같다.
  • 두 정점 A와 B사이의 거리는 A에서 시작해서 B에서 끝나는 경로에 있는 서로 다른 간선의 개수와 같다.

예제 입력 1

3
3
1 2
2 3
0 0 0
4
1 2
2 3
2 4
0 1 0 0
6
1 2
2 3
2 4
4 5
4 6
1 0 0 1 1 0

예제 출력 1

1
-1
2