|
Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
Автор: Павел Кузнецов, ПГУ.
There are N towns in Byteland. One can move between towns by roads
only. The road network is very compact, but also effcient enough to meet
all the requirements, i.e. there are N-1 roads and one can get
from any town to any other one. All roads are two way roads, i.e. you can move
in both directions. In order to improve citizens knowledge about roads that
connect their town with other towns it was decided to paint all the roads
with some colors. The only constraint is that no town should have two roads
connected to it that have the same color. Let's mark all M available
colors with positive integers, i.e. 1, 2, 3, ... , M. Painting any
road to color i costs exactly Ci Byteland rubles.
You are given a map with all towns and roads between them. Write a program
that finds a way to paint all the roads so that the total cost is minimal,
or says that it's impossible.
Input
The first line of input contains two integers N and M,
separated by space - the number of towns in Byteland and the number of
colors, correspondingly (1 ≤ M < N ≤ 50). The
following (N - 1) lines describe the roads. Each line contains
two integers A and B, separated by spaces. These are the
numbers of towns connected by the road. Towns are numbered from 1 to N
(1 ≤ A,B ≤ N). Next M lines contain the
costs of correspondent colors Ci
(1 ≤ Ci ≤ 106).
Output
If it's impossible to paint all the roads as described in the statement,
output one number -1. Otherwise, the first line should contain a single
integer - the minimal cost of painting in rubles. The following N-1
lines should contain the colors of each road in the same order, as the
roads appear in the input. Colors are numbered from 1 to M.
If there are several solutions, you may output any of them.
|
Input 1
|
Output 1
|
2 1
1 2
1
|
1
1
|
|
Input 2
|
Output 2
|
3 2
1 2
1 3
2
1
|
3
2
1
|
|
Input 3
|
Output 3
|
3 1
1 2
1 3
2
|
-1
|
Для отправки решений необходимо выполнить вход.
|