入力で与えられるグラフを \(G\) とします。
簡単のため、まずは \(G\) が連結な場合を考えます。まず、次の事実が成り立ちます。

ランプがついている個数は常に偶数個である。\((\ast)\)

(証明) 操作を 1 回行うごとに、ついているランプの個数は 2 個減るか変わらないか 2 個増えるかのいずれかで、操作前と操作後でついているランプの個数の偶奇は変わりません。よって初期状態でついているランプの個数が 0 個であることと合わせると、どのように操作してもついているランプの個数は偶数個のままです。(証明終わり)

この事実を利用すると、次の命題が証明できます。

\(K\) が偶数であることが、答えが Yes であるための必要十分条件である。

(証明) 必要性と十分性の 2 つに分けて示します。

必要性 : 対偶を取って「\(K\) が奇数であるならば、答えは No である」という命題を示すことにすると、\((\ast)\) より \(K\) が奇数の場合は答えは No であることがわかります。以上より必要性は示されました。

十分性 : 「\(K\) が偶数ならば答えは Yes である」という命題を示します。
\(N\) 以下の最大の偶数を \(X\) とします。簡単のため、はじめに「\(K = X\) ならば答えは Yes である」という命題を証明します。

\(K = X\) の時、以下のアルゴリズムに従って操作を行うことで、\(M\) 回以下の操作で \(K = X\) を達成することが出来ます。

• \(G\) の部分グラフのうち頂点 \(1\) を根とする根付き木を \(1\) つ取り \(T\) とする。
• 以下の操作を \(T\) が \(1\) 頂点のグラフになるまで繰り返す。
  • まず、\(T\) の葉を 1 つ選び \(v\) とする。\(v\) と隣接する辺を \(e\) とする。
  • \(v\) に載っているランプが消えている場合、\(e\) を選んで操作を行う。
  • その後、\(v\) および \(e\) を \(T\) から取り除く。

(アルゴリズムが正当である証明) 操作によって \(G\) の頂点のうち頂点 \(1\) 以外の頂点に載っているランプはついた状態になります。(頂点 \(1\) に載っているランプはついているかどうか不明) よって操作を終了した時点でついているランプの \(N-1\) 個または \(N\) 個です。一方、\((\ast)\) より操作によってついているランプの個数は常に偶数です。よって、操作後は「\(N-1\) と \(N\) のうち偶数である方」の個数だけランプがついていることになり、この値は \(X\) と一致します。 また、操作によって辺ごとに高々 1 回しか操作で選ばないため、操作を行う回数は辺の本数で抑えられています。 (証明終わり)

\(K\) が \(X\) でない偶数の場合を考えます。この時 \(0 \leq K \lt X\) です。 上に説明したアルゴリズムに従って操作を行うことを考えます。操作を 1 回行うごとについているランプの個数は変わらないか 2 個増えるかのいずれかです。(\(v\) に載っているランプは消えているため 2 個減ることはあり得ない。)また、\(0\) 個から始めて \(X\) 個で操作を終えるため、操作の途中においては \(0\) 以上 \(X\) 以下の全ての偶数 \(x\) について「ランプがちょうど \(x\) 個ついている」という状態が存在することになります。よって、必ずどこかの瞬間でついているランプの個数がちょうど \(K\) 個になる瞬間があるため、その時点でアルゴリズムを打ち切って操作を終了すれば Yes である条件を満たします。以上より十分性を証明できました。(証明終わり)

以上より \(K\) が Yes になる条件がわかりました。また、操作手順の構成も命題の証明において説明した方法を使えば \(\mathrm{O}(N + M)\) の計算量で動作するアルゴリズムを構成できるので、この問題を高速に解くことが出来ます。(実装においては、 DFS の帰りがけ順に辺を使っていく方針が簡潔に実装できます。詳しくは実装例を参考にしてください。)

\(G\) が連結でない場合も同様の解法で解くことが出来ます。\(G\) に含まれる各連結グラフごとに \(X\) を計算して足し合わせたものを \(Y\) とします。\(K\) が奇数、または \(Y\) より大きい時は明らかに答えは No です。逆にそうでない場合は、グラフが連結の場合と同様の議論が成り立ちます。すなわち、初期状態 (ついているランプが \(0\) 個の状態) から \(Y\) 個ついている状態になるまでのどこかのタイミングでちょうど \(K\) 個のランプがついた状態になるので、そのタイミングで操作を打ち切ればよいです。

計算量は \(\mathrm{O}(N + M)\) で十分高速です。

• 実装例(C++)

#include <iostream>
#include <vector>
using namespace std;

int main() {
  int N, M, K;
  cin >> N >> M >> K;

  vector<vector<pair<int, int>>> G(N);
  for (int i = 1; i <= M; i++) {
    int u, v;
    cin >> u >> v;
    --u, --v;
    G[u].emplace_back(v, i);
    G[v].emplace_back(u, i);
  }

  int Y = 0;
  vector<int> ans, vis(N), lamp(N);
  for (int i = 0; i < N; i++) {
    auto dfs = [&](auto rc, int c) -> void {
      vis[c] = 1;
      for (auto& [d, id] : G[c]) {
        if (vis[d]) continue;
        rc(rc, d);
        if (lamp[d] == 0 and Y < K) {
          Y -= lamp[d] + lamp[c];
          lamp[d] ^= 1, lamp[c] ^= 1;
          Y += lamp[d] + lamp[c];
          ans.push_back(id);
        }
      }
    };
    if (!vis[i]) dfs(dfs, i);
  }

  if (K != Y) {
    cout << "No" << endl;
  } else {
    cout << "Yes" << endl;
    cout << ans.size() << endl;
    for (int i = 0; i < (int)ans.size(); i++) cout << (i ? " " : "") << ans[i];
    cout << endl;
  }
}