KOI국에는 N개의 도시가 있어서, 1번부터 N번까지의 번호가 붙어있다. 또한, KOI국에는 N−1개의 국도가 있다. i 번째(1≤i≤N−1) 국도는 Ai번 도시와 Bi번 도시를 양방향으로 잇는다. 어떤 두 도시에 대해서도, 국도 몇개를 이용하면 서로 오가는 것이 가능하다.

현재, KOI국은 1번부터 K번까지의 번호가 붙어있는 K개의 주로 나뉘어 있다. j번 (1≤j≤N)도시는 Sj번 주에 속한다. 모든 주에는 적어도 하나의 도시가 속해 있다.

KOI국의 대통령인 준혁이는, 이 나라가 분열하지 않을까 걱정이 되었다. 다음 조건을 모두 만족하도록 모든 도시를 2개의 그룹 X, Y로 나누는 것이 가능할 때, KOI국은 분열가능한 상태라고 말한다.

- 모든 도시는 그룹 X혹은 그룹 Y에 속한다. - 그룹 X에는 적어도 하나의 도시가 속해 있다. - 그룹 Y에는 적어도 하나의 도시가 속해 있다. - 모든 주에 대해서, 그 주에 있는 모든 도시는 모두 같은 그룹에 속해 있다. - 그룹 X에 속한 어떤 두 도시에 대해서도, 그룹 X에 속한 도시만을 경유해서 서로 오가는 것이 가능하다. - 그룹 Y에 속한 어떤 두 도시에 대해서도, 그룹 Y에 속한 도시만을 경유해서 서로 오가는 것이 가능하다.

준혁이는 KOI국이 분열가능하지 않은 상태를 만들기 위해, 주를 합병하려고 한다. 한번의 합병은 두개의 주를 골라서 합치는 것을 말한다. 새로운 주는, 기존의 두 주에 속해 있던 도시들이 속해있다. 준혁이는 주를 최소한의 횟수만큼 합병하여 KOI국을 분열가능하지 않은 상태로 만들고 싶어한다.

도시와 국도의 위치, 현재 어떤 도시가 어떤 주에 속해있는가에 대한 상태가 주어졌을 때, KOI국이 분열가능하지 않은 상태로 만들기 위한 합병의 최소 횟수를 구하는 프로그램을 작성하여라.

1 <= N <= 500000

1 <= K <= N

1 <= A_i <= N (1 <= i <= N-1)

1 <= B_i <= N (1 <= i <= N-1)

1 <= S_i <= K (1 <= i <= N)

#5037 upload 25 done 5 how_to_reg 5

합병 timer 3s memory 256MB

#5037

합병 3s 256MB