Эйлеров цикл (путь)

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1500;
const int M = 100005;
vector <pair<int, int>> a[N], g;
vector <int> ans;
int dead[M];

void dfs(int u) {
    while (!a[u].empty()) {
        int v = a[u].back().first;
        int e = a[u].back().second;
        a[u].pop_back();
        if (dead[e]) continue;
        dead[e] = 1;
        dfs(v);
        ans.push_back(u);
    }
}

void solve() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        int sz;
        cin >> sz;
        while (sz--) {
            int k, t;
            cin >> k >> t;
            g.emplace_back(i, k);
        }
    }
    int cur = 0;
    for (auto i : g) {
        int u = i.first;
        int v = i.second;
        if (u < v) {
            a[u].emplace_back(v, cur);
            a[v].emplace_back(u, cur);
            cur++;
        }
    }
    vector <int> nch;
    for (int i = 1; i <= n; ++i) {
        if (a[i].size() % 2) {
            nch.push_back(i);
        }
    }
    if (nch.size() == 0) {
        ans.push_back(1);
        dfs(1);
        cout << ans.size() - 1 << '\n';
        for (int i : ans) {
            cout << i << ' ';
        }
    }
    else {
        pair <int, int> Add = {nch[0], nch[1]};
        if (nch[0] > nch[1]) swap(nch[0], nch[1]);
        a[Add.first].emplace_back(Add.second, cur);
        a[Add.second].emplace_back(Add.first, cur);
        ans.push_back(1);
        dfs(1);
        for (int i = 1; i < ans.size(); ++i) {
            int mn = min(ans[i - 1], ans[i]);
            int mx = max(ans[i - 1], ans[i]);
            pair <int, int> ty = {mn, mx};
            if (ty == Add) {
                vector <int> vyv;
                for (int j = i; j < ans.size() - 1; ++j)
                    vyv.push_back(ans[j]);
                for (int j = 0; j < i; ++j)
                    vyv.push_back(ans[j]);
                cout << vyv.size() - 1 << '\n';
                for (int i : vyv)
                    cout << i << ' ';
                exit(0);
            }
        }
    }
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    solve();
    return 0;
}