ר

11 http:\olimp.bstu.by
17
9:00 12:00

 
HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Sections > Unsorted > problem:


Many-coloured roads

Section problems

• Chessboard Pattern
• Galls village
• Sequence
• Bishops
• Polygons
• String manipulations
• Lawyers Council
• Math and Soldiers
• Many-coloured roads
• What about judges?
• Liars and Knights
• Interesting permutations
• Kovrov
• Points
• Roads
• Brackets
• Triangles

Feedback

If you notice incorrect translations in Contester, please let author know.

Time limit 2000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb.
: , .

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