lessons/参考实现/01-欧拉路径/CodeForces-723E.cpp

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

struct AdjEdge { int to, id; };

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int tests;
    cin >> tests;
    while (tests--) {
        int n, m;
        cin >> n >> m;
        vector<vector<AdjEdge>> adj(n + 1);
        vector<int> degree(n + 1, 0);
        vector<pair<int, int>> original(m);
        vector<int> a, b;
        a.reserve(m + n); b.reserve(m + n);

        auto add_edge = [&](int u, int v) {
            int id = static_cast<int>(a.size());
            a.push_back(u); b.push_back(v);
            adj[u].push_back({v, id});
            adj[v].push_back({u, id});
        };
        for (int id = 0; id < m; ++id) {
            int u, v;
            cin >> u >> v;
            original[id] = {u, v};
            add_edge(u, v);
            ++degree[u]; ++degree[v];
        }

        int best = 0;
        for (int v = 1; v <= n; ++v) {
            if (degree[v] % 2 == 0) ++best;
            else add_edge(0, v);
        }

        vector<bool> used(a.size(), false);
        vector<size_t> cursor(n + 1, 0);
        vector<pair<int, int>> direction(m, {-1, -1});
        for (int start = 0; start <= n; ++start) {
            while (cursor[start] < adj[start].size() && used[adj[start][cursor[start]].id]) {
                ++cursor[start];
            }
            if (cursor[start] == adj[start].size()) continue;
            vector<int> st{start};
            while (!st.empty()) {
                int v = st.back();
                while (cursor[v] < adj[v].size() && used[adj[v][cursor[v]].id]) {
                    ++cursor[v];
                }
                if (cursor[v] == adj[v].size()) {
                    st.pop_back();
                    continue;
                }
                AdjEdge e = adj[v][cursor[v]++];
                if (used[e.id]) continue;
                used[e.id] = true;
                if (e.id < m) direction[e.id] = {v, e.to};
                st.push_back(e.to);
            }
        }

        cout << best << '\n';
        for (auto [u, v] : direction) cout << u << ' ' << v << '\n';
    }
}