#P18517. Balance

Balance

Balance

Little Cyan Fish 正在 Qingyu Xiao 的指导下练习平衡。给定一个连通无向图 G=(V,E)G=(V,E),有 nn 个顶点,编号从 11 到 nn,以及 mm 条边。顶点 ii 上有一个整数标签 aia_i。

你可以任意多次交换任意两个顶点的标签。能否重新安排这些标签,使得

$$\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?$$

如果可以,请给出一种安排。

图可能含有连接同一对顶点的多条边,但没有自环。求和时每条边都要单独计入,包括平行边。交换不改变标签的多重集。

输入格式

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

对于每个测试用例:

  • 第一行包含 n,mn,m,满足 2≤n≤1052\le n\le10^5、n−1≤m≤2⋅105n-1\le m\le2\cdot10^5。
  • 接下来 mm 行每行包含 u,vu,v,表示一条无向边,1≤u,v≤n1\le u,v\le n,u≠vu\ne v。保证图连通,允许平行边。
  • 下一行包含 nn 个整数 a1,…,ana_1,\ldots,a_n,满足 1≤ai≤n1\le a_i\le n。

保证所有测试用例的 nn 之和不超过 5⋅1055\cdot10^5,mm 之和不超过 10610^6。

输出格式

每个测试用例:若不存在满足条件的重新安排,输出一行 No;否则先输出一行 Yes,然后输出一行 nn 个整数,依次为重新安排后各顶点的标签。标签多重集必须与输入相同,且必须满足原不等式。若有多个方案,可输出任意一个。

原样例

输入:

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