Let \(G\) be the graph given by the input.
For simplicity, we first assume that \(G\) is connected. We have the following fact:

The number of lit lamps is always even. \((\ast)\)

(Proof) The number of lit lamps increases by two, remains the same, or decreases by two, for every operation; namely, its parity is invariant by the operation. Since there are zero lit lamps in the initial state, there are an even number of lit lamps after any sequence of operations. (End of proof)

By this fact, we can prove the following fact:

\(K\) is even if and only if the answer is Yes.

(Proof) We show the necessity and sufficiency separately.

Necessity: the contraposition, “if \(K\) is odd, then the answer is No,” immediately follows the proposition \((\ast)\). Thus, the necessity is shown.

Sufficiency: we will prove that if \(K\) is even, then the answer is Yes.
Let \(X\) be the maximum even number not greater than \(N\). For simplicity, we first show that if \(K = X\), then the answer is Yes.

When \(K = X\), we can achieve \(K = X\) by at most \(M\) operations by following the algorithm below.

• Take a tree \(T\) rooted at vertex \(1\) that is a subgraph of \(G\).
• Repeat the following operation until \(T\) has one vertex.
  • First, take a leaf \(v\) of \(T\). Let \(e\) be the edge connected to \(v\).
  • If \(v\) is unlit, choose \(e\) to perform the operation.
  • Then, remove \(v\) and \(e\) from \(T\).

(Justification of the algorithm) By the operations, any lamps other than that on vertex \(1\) will be unlit. (Whether that on vertex \(1\) is lit or unlit is unknown.) Thus, when the algorithm terminates, there will be \((N-1)\) or \(N\) lit lamps. Meanwhile, \((\ast)\) guarantees that there are always an even number of lit lamps. Therefore, the number of lit lamps after the procedure is either \((N-1)\) or \(N\), whichever is even. This number coincides with \(X\). Also, each edge is chosen at most once by the operations, so the number of operations is bounded by the number of edges. (End of proof)

Now we consider the case where \(K\) is an even number not equal to \(X\). In this case, \(0 \leq K \lt X\). Consider operating according to the algorithm above. The number of lit lamps increases by two or remains the same by each operation. (The lamps on \(v\) is turned off, so it never decreases by two.) Also, we start from zero and finish with \(X\) lit lamps, for all even numbers \(x\) between \(0\) and \(X\) (inclusive), there exists a moment where there are exactly \(x\) lit lamps. Therefore, the number of lamps becomes \(K\) at some point; by aborting the algorithm there, it satisfies the condition of being Yes. Thus, the sufficiency has been proved. (End of proof)

Now we have figured out the condition that the answer is Yes. Moreover, we can also construct the procedure just as described in the proof, which works in \(\mathrm{O}(N + M)\) time, so the problem can be solved fast enough. (You can exploit the post-order of DFS (Depth-First Search) to implement simply. For more details, refer to sample code.)

Same thing applies when \(G\) is not connected. Let \(Y\) be the sum of \(X\) for each connected component of \(G\). If \(K\) is odd or greater than \(Y\), then the answer is obviously No. Otherwise, we can apply the same discussion as connected \(G\). That is, from the initial state to the state with \(Y\) lit lamps, there exists a moment with exactly \(K\) lamps, so we can abort the procedure.

The complexity is \(\mathrm{O}(N + M)\), which is fast enough.

• Sample code (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;
  }
}