#P17707. [2026年江苏省队集训]重绘现实
[2026年江苏省队集训]重绘现实
题面描述
你终于回到了你的小屋当中。
你的屋里有 棵焰灵草,起到保暖的作用。它们在燃烧的过程中会互相提供能量。具体来说,一共有 对形如 的链接,表示 会向 提供能量。
现在你需要对这些链接进行一些调整,达到一个特定的终止状态。你每次可以选择一条链接 ,将其反向,变为 。
但是有一个限制:任意时刻,对于任意一个焰灵草,需要存在至少一个其它焰灵草向它提供能量,否则它会永远地熄灭。窗外裹着雪花的呼啸声提醒着你,这是你现在最不希望发生的事情。
时间紧迫,你需要用最短的时间完成调整。即你需要给出一个步数最小的操作序列,将初始状态变为目标状态,或者报告无解。
你可以认为初始状态和最终状态均符合限制。
输入格式
第一行一个正整数 ,表示数据组数。
每组数据的第一行两个正整数 ,表示焰灵草的数量,和链接的数量。
接下来 行每行两个正整数 ,表示存在一条 的链接。
接下来一行一个长为 的 01 串 ,表示按照输入顺序中每一条链接在目标状态中是否需要反向。
输出格式
对于每组数据,如果无解,输出一行 No。
否则,第一行输出 Yes,第二行输出一个正整数 ,表示你需要的操作步数。
第三行输出一行 个正整数,表示你要依次反向的链接的编号。
输入输出样例
输入样例 #1
4
3 3
1 2
2 3
3 1
111
5 7
2 1
1 4
1 5
5 2
4 3
3 5
4 5
1010110
8 12
1 2
3 1
1 4
1 5
3 2
8 3
4 5
4 6
5 6
5 8
6 7
7 8
000011101001
4 4
3 1
1 4
3 2
4 3
0000
输出样例 #1
No
Yes
4
6 3 1 5
Yes
5
12 9 7 5 6
Yes
0
数据范围
对于所有数据,,,,且不存在两个链接 满足 或 。
贴心提示:不保证链接关系形成的图连通。
特殊限制如下,留空表示无特殊限制。
| 子任务编号 | 特殊性质 | 子任务分值 |
|---|---|---|
| 1 | , | |
| 2 | AB | |
| 3 | A | |
| 4 | B | |
| 5 |
特殊性质 A: 为全 1 串,即每条链接都需要反向。
特殊性质 B:,请注意 并无特殊限制。
如果对于一个子任务,你正确判断了每组数据是否有解,那么你可以获得这个子任务 的分数
在此基础上,如果你输出了一组正确的方案,满足 ,那么你可以获得这个子任务 的分数
在此基础上,如果你输出的 是可行的最小值,那么你可以获得这个子任务 的分数
请注意,如果你不打算输出正确的构造方式,你仍然需要输出一个格式合法的输出,如:
Yes
0
同时,本题在下发文件中提供了 chk.cpp,作为 checker 的参考实现。不保证与实际评测的 checker 相同。