#P17946. The Story of Company R

The Story of Company R

R 公司有 nn 名员工,每人住在一所房子里。有 mm 条双向道路连接这些房子,保证任意两所房子之间都能通过道路到达。直接由道路相连的员工互称邻居。

员工分为两类:经理(A 类)每天工作 aa 小时,工人(B 类)每天工作 bb 小时,且 a<ba<b。 你可以任意安排每名员工的非负实数开始时间 sis_i。A 类员工在 si+as_i+a 时结束,B 类员工在 si+bs_i+b 时结束。

一名员工满意,当且仅当同时满足:

  • 至少有一个邻居的开始时间严格早于自己的开始时间;
  • 至少有一个邻居的结束时间严格晚于自己的结束时间。

两条条件中的邻居可以是同一个人,也可以是不同的人。不满足上述条件的员工不满意。

请安排所有员工的开始时间,使不满意的员工数量尽可能少,并输出任意一种最优安排。

输入格式

第一行一个整数 TT(1≤T≤1051\le T\le10^5),表示测试用例数。

每个测试用例:

  • 第一行四个整数 n,m,a,bn,m,a,b,其中 1≤n,m≤5⋅1051\le n,m\le5\cdot10^5,1≤a<b≤1061\le a<b\le10^6。
  • 第二行一个长度为 nn、仅含 A 和 B 的字符串,第 ii 个字符表示第 ii 名员工的类型。
  • 接下来 mm 行,每行两个整数 u,vu,v(1≤u,v≤n1\le u,v\le n),表示一条道路。

图连通,没有重边或自环。所有测试用例的 ∑n≤5⋅105\sum n\le5\cdot10^5,∑m≤5⋅105\sum m\le5\cdot10^5。

输出格式

每个测试用例输出一行 nn 个非负整数 si′s'_i(0≤si′≤10180\le s'_i\le10^{18}),表示

si=si′106.s_i=\frac{s'_i}{10^6}.

若有多种最优安排,输出任意一种。不需要输出最少不满意人数。

样例 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