许多灯

题目描述

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

每个顶点上有一盏灯。初始时,所有灯都处于熄灭状态。

请判断是否可以通过执行以下操作 $0$ 到 $M$ 次(含两端),使得恰好有 $K$ 盏灯亮着。

选择一条边。设该边的两个端点为 $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 \le X \le M$
• $1 \le e_i \le M$

如果存在多个满足条件的操作序列,输出任意一个均视为正确。

样例

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

Yes
3
3 4 5

按照样例输出操作,过程如下:

选择边 $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)$ 等。(允许多次选择同一条边。)

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

No

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

Yes
3
10 9 6

数据范围

• $1 \le N \le 2 \times 10^5$
• $0 \le M \le \min\left( 2 \times 10^5, \frac{N(N-1)}{2} \right)$
• $0 \le K \le N$
• $1 \le u_i \lt v_i \le N$
• 给定的图是简单图。
• 所有输入值均为整数。

提示

答案不唯一,输出任意合法解即可。