给定大小为 n 的树和 m 条树上的简单路径。你需要给每条路径分配一个颜色 ci,使得任意两条颜色相同的路径,不经过相同的点。
求最少需要几种颜色,并构造方案。
输入格式
本题有多组测试数据。
输入的第一行包含一个整数 c,表示子任务编号。c=0 表示该测试点为样例。
输入的第二行包含一个整数 t,表示测试数据组数。
接下来依次输入每组测试数据,对于每组测试数据:
输入的第一行包含两个正整数 n,m。
接下来 n−1 行,第 i 行包含两个正整数 ui,vi,表示树的第 i 条边为 (ui,vi)。
接下来 m 行,第 i 行包含两个正整数 ai,bi,表示第 i 条路径为 ai 到 bi 的简单路径。
输出格式
对于每组测试数据:
第一行包含一个正整数 k,表示最少需要几种颜色。
第二行包含 m 个正整数,第 i 个数为第 i 条链的颜色 ci,你需要保证 1≤ci≤k。
如果你输出的 k 正确,ci 序列符合格式但不符合题目要求,可以获得该测试点 15% 的分数。
样例
输入
0 3 3 3 1 2 2 3 3 2 2 1 2 3 7 4 1 2 1 3 2 4 2 5 5 6 6 7 6 3 3 6 5 2 5 6 10 3 1 2 1 3 1 4 3 5 3 6 5 7 5 8 7 9 1 10 8 3 1 2 6 8
输出
3 1 2 3 4 1 2 3 4 2 1 1 2
数据范围
对于所有数据,1≤t≤105,1≤n,m,∑n,∑m≤5×105,1≤ui,vi,ai,bi≤n。
- subtask1 (3 pts):n,m≤5。
- subtask2 (14 pts):m≤5。
- subtask3 (9 pts):∀1≤i<n,ui=i,vi=i+1。
- subtask4 (20 pts):n,m≤1000,∑n,∑m≤5000。
- subtask5 (22 pts):∑n,∑m≤105。
- subtask6 (32 pts):无特殊限制。