QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 1024 MB Total points: 100
[+15]

# 9607. 熟练

Statistics

给定大小为 n 的树和 m 条树上的简单路径。你需要给每条路径分配一个颜色 ci,使得任意两条颜色相同的路径,不经过相同的点。

求最少需要几种颜色,并构造方案。

输入格式

本题有多组测试数据。

输入的第一行包含一个整数 c,表示子任务编号。c=0 表示该测试点为样例。

输入的第二行包含一个整数 t,表示测试数据组数。

接下来依次输入每组测试数据,对于每组测试数据:

输入的第一行包含两个正整数 n,m

接下来 n1 行,第 i 行包含两个正整数 ui,vi,表示树的第 i 条边为 (ui,vi)

接下来 m 行,第 i 行包含两个正整数 ai,bi,表示第 i 条路径为 aibi 的简单路径。

输出格式

对于每组测试数据:

第一行包含一个正整数 k,表示最少需要几种颜色。

第二行包含 m 个正整数,第 i 个数为第 i 条链的颜色 ci,你需要保证 1cik

如果你输出的 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

数据范围

对于所有数据,1t105,1n,m,n,m5×105,1ui,vi,ai,bin

  • subtask1 (3 pts):n,m5
  • subtask2 (14 pts):m5
  • subtask3 (9 pts):1i<n,ui=i,vi=i+1
  • subtask4 (20 pts):n,m1000,n,m5000
  • subtask5 (22 pts):n,m105
  • subtask6 (32 pts):无特殊限制。