20297번 - Confuzzle

문제

$N$개의 정점으로 구성된 가중치 없는 트리가 주어진다. 트리 상의 두 정점 사이의 거리는 두 정점 사이의 간선의 개수로 정의한다.

각 정점에는 수가 적혀 있으며, 적어도 두 정점은 같은 값임이 보장된다. 이때, 서로 같은 값이 쓰여 있는 두 정점 쌍 중 가장 거리가 가까울 때의 거리를 구해보자.

입력

첫째 줄에 트리의 정점의 개수 $N$이 주어진다. (2ドル \leq N \leq 100\ 000$)

둘째 줄에 각 정점의 고유한 값인 정수 $c_1, c_2, \cdots, c_N$이 주어진다. (1ドル \leq c_i \leq N$)

셋째 줄부터 $N - 1$개 줄에 걸쳐 각 줄마다 트리를 이루는 간선을 나타내는 정수 $u$와 $v$가 주어진다. 이는 $u$번 정점과 $v$번 정점을 잇는 간선이 존재함을 의미한다. (1ドル \leq u, v \leq N,ドル $u \neq v$)

출력

서로 같은 값을 갖는 두 정점 쌍 중 가장 거리가 가까울 때의 거리를 출력한다.

제한

힌트