Hopefully useful

#pragma optimize("O3")
#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
#include <cstring>
using namespace std;

const int N = 2000 + 7;

int n, m, k;
vector<int> g[N];
int order[N];

int cover[N];
int k_curr = 0;
int visited[N];
int cover_curr[N];

vector<int> g_red[N];

void check() {
    int k_copy = k_curr;
    memcpy(cover_curr, cover, sizeof(cover));
    memset(visited, 0, sizeof(visited));
    for (int i = 0; i < n; ++i) {
        g_red[i].clear();
        if (!cover_curr[i]) {
            for (int j : g[i]) {
                if (!cover_curr[j]) {
                    g_red[i].push_back(j);
                }
            }
        }
    }
    for (int t = 0; t < 2; ++t) {
        for (int i = 0; i < n; ++i) {
            if (!visited[i] && g_red[i].size() == t + 1) {
                int cur = i;
                int step = t;
                while (!visited[cur]) {
                    visited[cur] = true;
                    if (step & 1) {
                        cover_curr[cur] = true;
                        ++k_copy;
                        if (k_copy > k) {
                            return;
                        }
                    }
                    step++;
                    for (int j: g_red[cur]) {
                        if (j != cur) {
                            cur = j;
                            break;
                        }
                    }
                }
            }
        }
    }
//    for (int i = 0; i < n; ++i) {
//        g_red[i].clear();
//        if (!cover[i]) {
//            for (int j : g[i]) {
//                if (!cover[j]) {
//                    if (i < j) {
//                        cout << i + 1 << " " << j + 1 << "\n";
//                    }
//                }
//            }
//        }
//    }
    cout << "Yes\n";
    for (int i = 0; i < n; ++i) {
        if (cover_curr[i]) {
            cout << i + 1 << " ";
        } else if (k_copy < k) {
            cout << i + 1 << " ";
            ++k_copy;
        }
    }
    exit(0);
}

void req(int i) {
    if (i == n) {
        check();
        return;
    }
    int v = order[i];
    if (!cover[v]) {
        int power = 0;
        for (int u : g[v]) {
            if (!cover[u]) {
                ++power;
                if (power > 2) {
                    break;
                }
            }
        }
        if (power > 2) {
            cover[v]++;
            ++k_curr;
            if (k_curr <= k) {
                req(i + 1);
            }
            --k_curr;
            cover[v]--;

            for (int u: g[v]) {
                k_curr += (cover[u] == 0);
                ++cover[u];
            }
            if (k_curr <= k) {
                req(i + 1);
            }
            for (int u: g[v]) {
                --cover[u];
                k_curr -= (cover[u] == 0);
            }
            return;
        }
    }
    req(i + 1);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> m >> k;
    for (int i = 0; i < n; ++i) {
        order[i] = i;
    }
    for (int i = 0; i < m; ++i) {
        int v, u;
        cin >> v >> u;
        --v, --u;
        g[v].push_back(u);
        g[u].push_back(v);
    }
    std::random_device rd;
    std::mt19937 r(rd());

    std::shuffle(order, order + n, r);
    req(0);
    cout << "No\n";
    return 0;
}