ГлавнаяСборникиТурнирыРазделыФорумыУчастникиПечатьПомощьО системе

Сборники > Kovrov IT 2009 > задача:


D. Many-coloured roads

Задачи сборника

• A. Tetris 3D
• B. Knights of the Rook
• C. Meat store
• D. Many-coloured roads
• E. Kovrov
• F. Interesting permutations
• G. What about judges?
• H. Triangles
• I. ATM

Обратная связь

Если у вас есть предложения или пожелания по работе Contester, посетите форум сайта www.contester.ru.

Лимит времени 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,BN). 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

Для отправки решений необходимо выполнить вход.

www.contester.ru