#P17707. [2026年江苏省队集训]重绘现实

[2026年江苏省队集训]重绘现实

题面描述

你终于回到了你的小屋当中。

你的屋里有 nn 棵焰灵草,起到保暖的作用。它们在燃烧的过程中会互相提供能量。具体来说,一共有 mm 对形如 u→vu\to v 的链接,表示 uu 会向 vv 提供能量。

现在你需要对这些链接进行一些调整,达到一个特定的终止状态。你每次可以选择一条链接 u→vu\to v,将其反向,变为 v→uv\to u。

但是有一个限制:任意时刻,对于任意一个焰灵草,需要存在至少一个其它焰灵草向它提供能量,否则它会永远地熄灭。窗外裹着雪花的呼啸声提醒着你,这是你现在最不希望发生的事情。

时间紧迫,你需要用最短的时间完成调整。即你需要给出一个步数最小的操作序列,将初始状态变为目标状态,或者报告无解。

你可以认为初始状态和最终状态均符合限制。

输入格式

第一行一个正整数 TT,表示数据组数。

每组数据的第一行两个正整数 n,mn,m,表示焰灵草的数量,和链接的数量。

接下来 mm 行每行两个正整数 u,vu,v,表示存在一条 u→vu\to v 的链接。

接下来一行一个长为 mm 的 01 串 ss,表示按照输入顺序中每一条链接在目标状态中是否需要反向。

输出格式

对于每组数据,如果无解,输出一行 No。

否则,第一行输出 Yes,第二行输出一个正整数 0≤k≤10m0\le k\le10m,表示你需要的操作步数。

第三行输出一行 kk 个正整数,表示你要依次反向的链接的编号。

输入输出样例

输入样例 #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

数据范围

对于所有数据,3≤n≤m3\le n\le m,∑m≤2×105\sum m\le2\times10^5,1≤u,v≤n,u≠v1\le u,v\le n,u\neq v,且不存在两个链接 ui→vi,uj→vju_i\to v_i,u_j\to v_j 满足 (ui,vi)=(uj,vj)(u_i,v_i)=(u_j,v_j) 或 (ui,vj)=(uj,vi)(u_i,v_j)=(u_j,v_i)。

贴心提示:不保证链接关系形成的图连通。

特殊限制如下,留空表示无特殊限制。

子任务编号 特殊性质 子任务分值
1 n≤m≤16n\le m\le16,∑m≤3000\sum m\le3000 1111
2 AB 1414
3 A 1616
4 B 2626
5 3333

特殊性质 A:ss 为全 1 串,即每条链接都需要反向。

特殊性质 B:m≤300m\le300,请注意 ∑m\sum m 并无特殊限制。

如果对于一个子任务,你正确判断了每组数据是否有解,那么你可以获得这个子任务 25%25\% 的分数

在此基础上,如果你输出了一组正确的方案,满足 k∈[0,10m]k\in[0,10m],那么你可以获得这个子任务 60%60\% 的分数

在此基础上,如果你输出的 kk 是可行的最小值,那么你可以获得这个子任务 100%100\% 的分数

请注意,如果你不打算输出正确的构造方式,你仍然需要输出一个格式合法的输出,如:

Yes
0

同时,本题在下发文件中提供了 chk.cpp,作为 checker 的参考实现。不保证与实际评测的 checker 相同。

附加文件