#1867. 熟练

    ID: 1867 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest1826来源:qoj.ac数据:公开样例树上算法倍增

熟练

熟练

题目描述

标题: 熟练 - Problem - QOJ.ac

#9607. 熟练

Statistics

The problem was used in the following contests:

给定大小为 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):无特殊限制。

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

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