Kingdom Division

Time limit2sMemory limit1024 MB

Summary

Split a tree of N cities into P connected parts whose city values all sum to the same total, and report each city's part.

Level: Medium6 of 10
Topics: Tree, DFS, Greedy
Solved: No attempts yet

Problem

In a far away kingdom, there are $N$ cities numbered from $0$ to $N - 1$ . The cities are connected by $N - 1$ two-way roads. Each road connects exactly two cities, and there is a unique path between any pair of cities. Each city $i$ has a value $C[i]$ , which may be negative. The old king died without naming a successor, so a civil war broke out between $P$ lords (numbered from $0$ to $P - 1$ ) who want control of the kingdom. After a long and terrible war, the lords realized that none of them could beat all the others. They agreed to a truce and decided to divide the kingdom into $P$ parts, one per lord. The division must satisfy this rule: if two cities $a$ and $b$ are in the same part, every city on the unique path between them must also be in that part. Each lord must receive at least one city. No lord should get less than another, so every part must have the same value. The value of a part is the sum of $C$ over all cities in that part.

Input

The sample judge reads input in the following format:

line 1: N P
line 2: C[0] C[1] .. C[N - 1]
line 3: F[0] F[1] .. F[N - 2]
line 4: T[0] T[1] .. T[N - 2]

Output

The sample judge first writes a single line with the return value of division(N, P, C, F, T). The next line contains $N$ integers, which is the input to the parts(R) call.

Constraints

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

Examples1

Example 1

Input

5 3
-4 3 3 -1 -4
0 1 2 3
2 4 4 4

Expected output

1
0 1 0 2 1