题目描述

幼儿园打算买进 $n$ 个球形玩具。

目前商店有 $n$ 种球形玩具，每种球形玩具都有 $k$ 个，并且 $k$ 个颜色互不相同，并且价格各有差异，并且每种球形玩具，商店只允许买一个颜色。

现在幼儿园的老师打算通过 $n-1$ 个小朋友，来知道该如何购买这 $n$ 个球形玩具，于是老师拿了一张纸，让小朋友们写下自己想选的两种球形玩具，可是老师有要求：

• 每个小朋友需要写下两种不同的球形玩具，表示当前这位小朋友以后可以选择玩这两种球形玩具。
• $n$ 种球形玩具都会被写在纸上。
• 每种球形玩具只能买一个颜色。
• 小朋友不能写下重复的需求。

通过这张纸，老师可以得到一张小朋友们玩球形玩具的连通需求网。

为了让需求网更加精彩，老师想要让每一个小朋友可以选择的球形玩具颜色不同。

老师想知道，他购进$n$个球形玩具最少需要花费多少钱，以及每种球形玩具需要买哪种颜色。

输入格式

第一行输入两个整数 $n$ 和 $k$ ，表示有 $n$ 种球形玩具和每种球形玩具有 $k$ 个。

随后 $n$ 行，每行输入 $k$ 个整数：${a_{i,1}}，{a_{i,2}}，{a_{i,3}}，……，{a_{i,k}}$ ，其中${a_{i,j}}$表示颜色为 $j$ 的第$i$ 种球形玩具对应的价格。

随后 $n-1$ 行，每行输入两个整数 $u$ 和 $v$ ，表示第 $i$ 个小朋友写下的两种球形玩具，并且满足老师的要求。

输出格式

第一行输出一个整数 $ans$ ，表示老师最少需要花多少钱购进 $n$ 个球形玩具。

第二行输出 $n$ 个整数，每个整数用空格隔开，${c_1},{c_2},{c_3},……,{c_n}$ ，其中 ${c_i}$ 表示第 $i$ 种球形玩具需要购买的颜色。

特别地：

• 如果有多组球形颜色方案，任意输出一组即可。
• 如果没有球形颜色方案，输出-1。

输入输出样例 #1

输入 #1

3 2
10 2
3 10
4 10
1 2
1 3

输出 #1

9
2 1 1

说明/提示

对于 100 %的测试数据，$2 \leq n \leq 2\times 10^3 , 1 \leq k \leq 10^3,1 \leq {a_{i,j}} \leq 10^9$。