Submission #51484016

---

Source Code Expand

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

vector<vector<pair<int, int>>> G;
vector<int> ans;
vector<bool> vis, lamp;
int rest;

void dfs(int c) {
    vis[c] = true;
    for (auto& [d, id] : G[c]) {
        if (vis[d]) continue;
        dfs(d);
        if (rest <= 0) return;
        if (lamp[d]) continue;
        lamp[d] = true;
        lamp[c] = ! lamp[c];
        if (lamp[c]) { rest -= 2; }
        ans.push_back(id);
    }
}

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

    vector<vector<pair<int, int>>> G1(N);
    vector<bool> vis1(N), lamp1(N);
    G = G1;
    vis = vis1;
    lamp = lamp1;

    if (K % 1) { puts("No"); exit(0); }
    if (K == 0) { puts("Yes"); puts("0"); puts(""); exit(0); }

    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);
    }

    rest = K;
    for (int i = 0; i < N; i++) if (! vis[i]) dfs(i);

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

// 公式解説のコードを自分の理解のために整理した
// ら、WAもREも出るってどういうことなの…
// Kが奇数でも構わず計算するから、rest = -1 で終わることがある、ということで rest == 0 (K==Y) で判定するようにして
// 最後にREが2個残った。
// ans.size() == 0 の例外的な場合かぁ…

Submission Info

Judge Result