#P18517. Balance
Balance
Balance
Little Cyan Fish 正在 Qingyu Xiao 的指导下练习平衡。给定一个连通无向图 ,有 个顶点,编号从 到 ,以及 条边。顶点 上有一个整数标签 。
你可以任意多次交换任意两个顶点的标签。能否重新安排这些标签,使得
$$\sum_{(u,v)\in E}|a_u-a_v|\le \max_{1\le i\le n}a_i-\min_{1\le i\le n}a_i?$$如果可以,请给出一种安排。
图可能含有连接同一对顶点的多条边,但没有自环。求和时每条边都要单独计入,包括平行边。交换不改变标签的多重集。
输入格式
第一行包含整数 ,表示测试用例数,。
对于每个测试用例:
- 第一行包含 ,满足 、。
- 接下来 行每行包含 ,表示一条无向边,,。保证图连通,允许平行边。
- 下一行包含 个整数 ,满足 。
保证所有测试用例的 之和不超过 , 之和不超过 。
输出格式
每个测试用例:若不存在满足条件的重新安排,输出一行 No;否则先输出一行 Yes,然后输出一行 个整数,依次为重新安排后各顶点的标签。标签多重集必须与输入相同,且必须满足原不等式。若有多个方案,可输出任意一个。
原样例
输入:
5
5 4
1 2
2 3
3 4
4 5
1 2 3 4 5
5 4
1 2
1 3
1 4
1 5
1 2 3 4 5
5 4
1 2
1 3
1 4
1 5
1 2 2 2 3
5 6
1 2
1 2
2 3
3 4
4 5
3 5
1 2 1 2 1
2 2
1 2
1 2
1 2
输出:
Yes
5 4 3 2 1
No
Yes
2 2 2 3 1
Yes
2 2 1 1 1
No