#P18275. Exploration Boundary

Exploration Boundary

Exploration Boundary

最近,一篇讨论 Dijkstra 算法及其最优性的论文引起了 Fuyu 的注意。论文使用了一个称为探索边界的概念:在 Dijkstra 算法运行的某个时刻,已经被发现、进入优先队列,但最短距离尚未最终确定的顶点,组成当前的探索边界。

一次探索边界的更新

图中黑点表示最短距离已经确定的顶点,绿色点是当前探索边界,白点尚未发现。右图由左图确定距离源点为 22 的顶点、再更新它的邻居后得到。

更准确地说,考虑下面的 Dijkstra 算法。优先队列 QQ 对每个尚未确定距离但已经发现的顶点只保存一个元素,按当前距离排序;更新已有元素时执行减小键值操作,不重复插入同一个顶点。

S = 空集                         // 已经确定最短距离的顶点
Q = 空优先队列
所有 D[v] = 正无穷
D[s] = 0,把 s 放入 Q
while Q 非空:
    // 在这里取出 Q 中的顶点集合,它就是一次探索边界
    从 Q 取出当前距离最小的顶点 u
    把 u 加入 S
    对 u 的每个尚未加入 S 的邻居 v:
        如果 v 尚未进入 Q,把 v 以正无穷的距离放入 Q
        D[v] = min(D[v], D[u] + w(u,v))
        相应地更新 v 在 Q 中的键值

只有在每轮取出最小距离顶点之前,QQ 中的非空顶点集合才称为探索边界。特别地,最初的 {s}\{s\} 是探索边界;队列最终为空的集合不算。

对同一张无向图,使用不同的正边权,可以得到不同的探索边界。但一些边界即使分别可行、甚至互不相交,也无法在同一次 Dijkstra 运行中同时出现。

分别可行但不能同时出现的边界

给定一张连通无向图和若干希望出现的探索边界,固定源点 s=1s=1。请为每条边构造权值,使以下条件同时成立:

  • 每条边的权值都是 [1,109][1,10^9] 内的整数。
  • 任意两个不同顶点到顶点 11 的最短距离不同。因此,Dijkstra 的顶点出队顺序以及探索边界序列都是唯一的。
  • 给出的每个探索边界都在这一次从顶点 11 出发的 Dijkstra 运行中出现。

给定边界可以按任意顺序出现,也允许运行中出现未被指定的其他边界。如果无法构造,请报告无解。

输入格式

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

对每个测试用例:

  • 第一行两个整数 n,mn,m(2≤n≤2×1052\le n\le2\times10^5,1≤m≤2×1051\le m\le2\times10^5),表示顶点数和边数。
  • 接下来 mm 行,每行两个整数 u,vu,v(1≤u,v≤n1\le u,v\le n),表示一条无向边。
  • 接下来一行一个整数 kk(1≤k≤2×1051\le k\le2\times10^5),表示希望出现的探索边界数。
  • 接下来 kk 行,每行先给出整数 bib_i(1≤bi≤n1\le b_i\le n),随后给出 bib_i 个顶点编号,描述第 ii 个边界。同行中的顶点互不相同。

保证图连通、没有自环和重边,且同一测试用例中不存在两个完全相同的边界集合。不同边界可以有公共顶点,输入顺序不表示它们出现的顺序,集合内的编号顺序也没有含义。

同一个输入文件内,所有测试用例的 nn 之和、mm 之和、以及所有边界的大小 bib_i 之和,分别不超过 10610^6。

输出格式

对每个测试用例:

  • 如果存在方案,输出一行 Yes,下一行输出 mm 个整数,依照边在输入中出现的顺序给出它们的权值。每个权值必须在 [1,109][1,10^9] 内。
  • 如果不存在方案,只输出一行 No。

可以输出任意满足条件的方案。

样例输入

2
8 10
1 2
1 3
1 4
1 5
2 6
3 6
3 7
4 8
5 8
7 8
2
4 3 4 5 6
4 4 5 6 7
5 4
1 2
1 3
2 4
2 5
2
2 3 4
2 2 5

样例输出

Yes
1 2 3 5 3 5 4 5 6 3
No