왕국 분할

먼 옛날 왕국에 $N$개의 도시가 있으며, 번호는 $0$부터 $N-1$까지이다. 도시들은 $N-1$개의 양방향 도로로 연결되어 있고, 각 도로는 정확히 두 도시를 잇는다. 임의의 두 도시 사이에는 유일한 경로가 있다. 각 도시 $i$에는 값 $C[i]$가 있으며, 이 값은 음수일 수도 있다. 옛 국왕이 후계자를 정하지 않고 죽자, 왕국의 지배권을 노리는 $P$명의 영주(번호는 $0$부터 $P-1$까지) 사이에 내전이 일어났다. 길고 참혹한 전쟁 끝에 영주들은 어느 누구도 나머지 모든 영주를 이길 수 없다는 것을 깨달았다. 그들은 휴전에 합의하고, 왕국을 $P$개의 부분으로 나누어 영주마다 하나씩 맡기기로 했다. 분할은 다음 규칙을 지켜야 한다. 두 도시 $a$와 $b$가 같은 부분에 속하면, 둘 사이의 유일한 경로에 있는 모든 도시도 그 부분에 속해야 한다. 모든 영주는 반드시 적어도 한 도시를 받아야 한다. 어느 영주도 다른 영주보다 적게 받아서는 안 되므로, 모든 부분의 값은 같아야 한다. 부분의 값은 그 부분에 속한 도시들의 $C$ 값을 모두 더한 것이다.

샘플 채점기는 다음 형식으로 입력을 읽는다.

• 1번째 줄: N P
• 2번째 줄: C[0] C[1] .. C[N - 1]
• 3번째 줄: F[0] F[1] .. F[N - 2]
• 4번째 줄: T[0] T[1] .. T[N - 2]

샘플 채점기는 먼저 division(N, P, C, F, T)의 반환값을 한 줄로 출력한다. 다음 줄에는 parts(R) 호출의 입력이 되는 정수 $N$개를 출력한다.

$1 \le P \le N \le 100000$