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

图中黑点表示最短距离已经确定的顶点,绿色点是当前探索边界,白点尚未发现。右图由左图确定距离源点为 的顶点、再更新它的邻居后得到。
更准确地说,考虑下面的 Dijkstra 算法。优先队列 对每个尚未确定距离但已经发现的顶点只保存一个元素,按当前距离排序;更新已有元素时执行减小键值操作,不重复插入同一个顶点。
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 中的键值
只有在每轮取出最小距离顶点之前, 中的非空顶点集合才称为探索边界。特别地,最初的 是探索边界;队列最终为空的集合不算。
对同一张无向图,使用不同的正边权,可以得到不同的探索边界。但一些边界即使分别可行、甚至互不相交,也无法在同一次 Dijkstra 运行中同时出现。

给定一张连通无向图和若干希望出现的探索边界,固定源点 。请为每条边构造权值,使以下条件同时成立:
- 每条边的权值都是 内的整数。
- 任意两个不同顶点到顶点 的最短距离不同。因此,Dijkstra 的顶点出队顺序以及探索边界序列都是唯一的。
- 给出的每个探索边界都在这一次从顶点 出发的 Dijkstra 运行中出现。
给定边界可以按任意顺序出现,也允许运行中出现未被指定的其他边界。如果无法构造,请报告无解。
输入格式
第一行一个整数 (),表示测试用例数。
对每个测试用例:
- 第一行两个整数 (,),表示顶点数和边数。
- 接下来 行,每行两个整数 (),表示一条无向边。
- 接下来一行一个整数 (),表示希望出现的探索边界数。
- 接下来 行,每行先给出整数 (),随后给出 个顶点编号,描述第 个边界。同行中的顶点互不相同。
保证图连通、没有自环和重边,且同一测试用例中不存在两个完全相同的边界集合。不同边界可以有公共顶点,输入顺序不表示它们出现的顺序,集合内的编号顺序也没有含义。
同一个输入文件内,所有测试用例的 之和、 之和、以及所有边界的大小 之和,分别不超过 。
输出格式
对每个测试用例:
- 如果存在方案,输出一行
Yes,下一行输出 个整数,依照边在输入中出现的顺序给出它们的权值。每个权值必须在 内。 - 如果不存在方案,只输出一行
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