https://pintia.cn/problem-sets/994805046380707840/exam/problems/994805072641245184?type=7&page=0

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> PII;
typedef vector<long long> VI;

#define INF 0x3f3f3f3f
#define endl '\n'
#define N 2000100
const int mod = 1e9 + 7;

ll ksm(ll a, ll b) {
    ll ans = 1;
    for (; b; b >>= 1LL) {
        if (b & 1) ans = ans * a % mod;
        a = a * a % mod;
    }
    return ans;
}

ll lowbit(ll x) {
    return -x & x;
}

int p[N], si[N];
int find(int x) {
    if (x == p[x])return p[x];
    p[x] = find(p[x]);
    return p[x];
}
//size[find(b)] += size[find(a)];
//p[find(a)] = find(b);

int h1, cn1, cn2;
vector<PII> s(N);
int a[N], b[N];
int vis[N];
int n;


void solve() {
    cin >> h1 >> n;

    for (int i = 1; i <= n;  i++) {
        int x, y, z;
        cin >> x >> y >> z;

        s[x].first = y;
        s[x].second = z;
    }

    while (h1 != -1) {
        int x = abs(s[h1].first);

        if (!vis[x]) {
            a[cn1 ++] = h1;
            a[cn1] = -1;
            vis[x] = 1;
        }

        else {
            b[cn2 ++] = h1;
            b[cn2] = -1;
        }

        h1 = s[h1].second;
    }

    for (int i = 0; i < cn1; i++) {
        printf("%05d %d ", a[i], s[a[i]].first);
        if (i < cn1 - 1)printf("%05d", a[i + 1]);
        else cout << -1;
        cout << endl;

    }

    for (int i = 0; i < cn2; i++) {
        printf("%05d %d ", b[i], s[b[i]].first);
        if (i < cn2 - 1)printf("%05d", b[i + 1]);
        else cout << -1;
        cout << endl;
    }


}

signed main() {

//  ios::sync_with_stdio(false);
//  cin.tie(0), cout.tie(0);

    int T = 1;
//  cin >> T;
    while (T --)

        solve();

    return 0;
}