AT_abc345_f [ABC345F] Many Lamps

题目描述

有一个 $N$ 个顶点 $M$ 条边的简单图，顶点编号为 $1$ 到 $N$，边编号为 $1$ 到 $M$。第 $i$ 条边连接顶点 $u_i$ 和顶点 $v_i$。

每个顶点上都有一个灯，初始时所有灯都是关闭的。

你可以进行如下操作 $0$ 次或至多 $M$ 次：

• 选择一条边。设该边的两个端点为 $u$ 和 $v$。将 $u$ 和 $v$ 上的灯的状态反转（如果灯是亮的就关掉，如果是关的就打开）。

请判断是否可以通过上述操作，使得恰好有 $K$ 个灯是亮着的。

如果可以，请输出一种可行的操作方案。

输入格式

输入通过标准输入给出，格式如下：

$N$ $M$ $K$
$u_1$ $v_1$
$u_2$ $v_2$
$\vdots$
$u_M$ $v_M$

输出格式

如果无法使恰好 $K$ 个灯亮着，输出 No。

如果可以，先输出 Yes，然后输出操作方案，格式如下：

$X$ $e_1$ $e_2$ $\dots$ $e_X$

其中，$X$ 表示操作次数，$e_i$ 表示第 $i$ 次操作选择的边的编号。要求满足：

• $0 \leq X \leq M$
• $1 \leq e_i \leq M$

如果存在多种满足条件的操作方案，输出任意一种均可。

输入输出样例 #1

输入 #1

5 5 4
1 2
1 3
2 4
3 5
1 5

输出 #1

Yes
3
3 4 5

输入输出样例 #2

输入 #2

5 5 5
1 2
1 3
2 4
3 5
1 5

输出 #2

No

输入输出样例 #3

输入 #3

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

输出 #3

Yes
3
10 9 6

说明/提示

限制条件

• $1 \leq N \leq 2 \times 10^5$
• $0 \leq M \leq \min\left(2 \times 10^5, \frac{N(N-1)}{2}\right)$
• $0 \leq K \leq N$
• $1 \leq u_i < v_i \leq N$
• 输入保证图是简单图
• 所有输入值均为整数

样例解释 1

按照输出样例的操作顺序，状态如下：

• 选择第 $3$ 条边。点 $2$ 和点 $4$ 上的灯被点亮。
• 选择第 $4$ 条边。点 $3$ 和点 $5$ 上的灯被点亮。
• 选择第 $5$ 条边。点 $1$ 上的灯被点亮，点 $5$ 上的灯被关闭。

所有操作结束后，点 $1,2,3,4$ 上的灯是亮的，因此该操作方案满足条件。

其他满足条件的方案还包括 $X=4,\ (e_1,e_2,e_3,e_4)=(3,4,3,1)$ 等（同一条边可以选择多次）。

由 ChatGPT 4.1 翻译