lessons/参考实现/01-欧拉路径/CodeForces-1361C.cpp

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

struct Step {
    int edge;
    int from;
    int to;
};

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

    int n;
    cin >> n;
    vector<int> a(n), b(n);
    for (int i = 0; i < n; ++i) cin >> a[i] >> b[i];

    for (int bits = 20; bits >= 0; --bits) {
        int vertices = 1 << bits;
        int mask = vertices - 1;
        vector<vector<pair<int, int>>> graph(vertices);
        vector<int> degree(vertices, 0);
        for (int i = 0; i < n; ++i) {
            int u = a[i] & mask;
            int v = b[i] & mask;
            graph[u].push_back({v, i});
            graph[v].push_back({u, i});
            ++degree[u];
            ++degree[v];
        }
        bool possible = true;
        int start = a[0] & mask;
        for (int v = 0; v < vertices; ++v) {
            if (degree[v] & 1) possible = false;
            if (degree[v] != 0) start = v;
        }
        if (!possible) continue;

        vector<int> iterator(vertices, 0);
        vector<char> used(n, false);
        vector<int> vertex_stack{start};
        vector<Step> entering;
        vector<Step> tour;
        while (!vertex_stack.empty()) {
            int v = vertex_stack.back();
            while (iterator[v] < static_cast<int>(graph[v].size())
                   && used[graph[v][iterator[v]].second]) {
                ++iterator[v];
            }
            if (iterator[v] == static_cast<int>(graph[v].size())) {
                vertex_stack.pop_back();
                if (!entering.empty()) {
                    tour.push_back(entering.back());
                    entering.pop_back();
                }
                continue;
            }
            auto [to, edge] = graph[v][iterator[v]++];
            if (used[edge]) continue;
            used[edge] = true;
            vertex_stack.push_back(to);
            entering.push_back({edge, v, to});
        }
        if (static_cast<int>(tour.size()) != n) continue;
        reverse(tour.begin(), tour.end());

        cout << bits << '\n';
        for (const Step &step : tour) {
            int left = 2 * step.edge + 1;
            int right = 2 * step.edge + 2;
            if ((a[step.edge] & mask) != step.from) swap(left, right);
            cout << left << ' ' << right << ' ';
        }
        cout << '\n';
        return 0;
    }
}