#P17946. The Story of Company R
The Story of Company R
R 公司有 名员工,每人住在一所房子里。有 条双向道路连接这些房子,保证任意两所房子之间都能通过道路到达。直接由道路相连的员工互称邻居。
员工分为两类:经理(A 类)每天工作 小时,工人(B 类)每天工作 小时,且 。 你可以任意安排每名员工的非负实数开始时间 。A 类员工在 时结束,B 类员工在 时结束。
一名员工满意,当且仅当同时满足:
- 至少有一个邻居的开始时间严格早于自己的开始时间;
- 至少有一个邻居的结束时间严格晚于自己的结束时间。
两条条件中的邻居可以是同一个人,也可以是不同的人。不满足上述条件的员工不满意。
请安排所有员工的开始时间,使不满意的员工数量尽可能少,并输出任意一种最优安排。
输入格式
第一行一个整数 (),表示测试用例数。
每个测试用例:
- 第一行四个整数 ,其中 ,。
- 第二行一个长度为 、仅含 A 和 B 的字符串,第 个字符表示第 名员工的类型。
- 接下来 行,每行两个整数 (),表示一条道路。
图连通,没有重边或自环。所有测试用例的 ,。
输出格式
每个测试用例输出一行 个非负整数 (),表示
若有多种最优安排,输出任意一种。不需要输出最少不满意人数。
样例 1
输入
5
2 1 1 5
AA
1 2
3 3 1 5
ABA
1 2
1 3
2 3
5 4 2 4
BABBB
1 2
1 5
2 3
2 4
6 9 1 5
BABBAB
1 2
1 3
1 4
2 6
3 4
3 5
3 6
4 5
5 6
7 7 2 5
BBAAABB
1 2
1 3
1 5
2 4
3 6
3 7
6 7
输出
0 1
1 0 2
2 1 0 3 4
2 3 1 4 4000005 0
3000003 3000004 3000002 3000005 3000006 1 0