Untitled

#include <bits/stdc++.h>
using namespace std;
#define MAXN 505

vector<int> g[MAXN];
int match[MAXN];
bitset<MAXN> vis;

bool Try(int now) {
    for (auto i : g[now]) {
        if (!vis[i]) {
            vis[i] = true;
            if (!match[i] || Try(match[i])) {
                match[i] = now;
                return true;
            }
        }
    }
    return false;
}

int main() {
    int n, m;
    cin >> n >> m;

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        u++, v++;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    int matchCnt = 0;
    for (int i = 1; i <= n; i++) {
        vis.reset();
        if (Try(i)) matchCnt++;
    }
    cout << matchCnt / 2 << '\n';

    vector<bool> output(n, false);
    vector<int> vertex_cover;
    for (int i = 1; i <= n; ++i) {
        if (match[i]  && !output[i]) {
            output[match[i]] = output[i] = true;
            vertex_cover.push_back(i);
            printf("%d %d\n", match[i] - 1, i - 1);
        }
    } 
    for(int i=1; i<=n; i++) {
        if (!output[i]) vertex_cover.push_back(i);
    }
    cout << vertex_cover.size() << '\n';
    for(auto i : vertex_cover) cout << i - 1 << ' ';

}