信息学竞赛选手眼中的树和普通人眼中的树是不同的，但在这道题中，两种都是正确的。

p6pou热爱大自然，经常在树林里散步。每当他注视着树林中的树木，都会去欣赏树的大小、节点的度数、若隐若现的规律等等。在舒适的春天里，p6pou更加的被树木所吸引——树木展现出了不同的颜色！

有一天，p6pou观察到一棵有$N$个节点的树，树上每个节点都有一种颜色。因为某些不可名状的原因，p6pou盯着这棵树看了很长时间，并写下了一个$N\times N$的矩阵。对于树上任意两个节点间的简单路径，p6pou都在矩阵的对应位置记录了路径上不同颜色数量（包括端点）。可惜的是，p6pou专注于欣赏这棵树，只记录下了这个矩阵，没有记录下这个树的形态。

p6pou需要你的帮助，根据这个矩阵中的数据来确定树的形态和每个节点的颜色，颜色用$1\sim N$的整数表示。p6pou可以向你保证，他记录的矩阵一定是对的，换句话说，一定存在一棵符合条件的树。

第一行一个整数，表示子任务的编号，数值可能为$1,2,3$。

第二行一个整数$N(1\leq N\leq 3000)$，表示树的节点数量。节点编号为$1,2,\dots,N$。

接下来是一个$N$行$N$列的矩阵，第$i$行第$j$列的数表示节点$i$和节点$j$路径上的不同颜色数量。

第一行输出$N$个空格间隔的整数，依次是每个节点的颜色，颜色应当是$1\sim N$的整数。

接下来$N-1$行，每行有两个整数$A,B$，表示树的一条边。边、同一条边两个端点都可以按任意的顺序输出。

子任务1（18分）对于20%的数据：矩阵中所有数都是$1$或$2$；
子任务2（25分）对于28%的数据：当树的形态是$N-1$条边都连接编号相差$1$的两个节点时，存在符合题意的染色方案；
子任务3（57分）对于52%的数据：没有额外限制。
（本题有25个测试点，每个测试点4分。除了上述特殊限制外，$n$的大小无梯度）

本题评测需要花费的时间较长(例如nodgd的程序测了5min才测完)，请尽量确保AC再提交(例如先去LOJ上AC了再来NKOJ提交)，以减轻评测机工作压力。