Source Code
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <set>
#include <stack>
#include <numeric>
#include <chrono>
#include <random>
#include <bitset>
#include <tuple>
#include <queue>
#include <map>
#include <unordered_map>
#include <cstring>
#include <cassert>
#include <climits>
#include <complex>
#include <math.h>
using namespace std;

const int N = 5e5 + 10, mod = 1e9 + 7;

map<int, vector<int>> mp[N];
vector<int> ids[N], sids[N];
int n, m, cnt[N];
bool vis[N];

vector<int> bigvec;
int calcBigger (int i) {
    bigvec.clear();
    vector<pair<int, int>> szs;
    vector<int> b;

    for (auto it : mp[i]) {
        szs.push_back({cnt[it.first], it.second.size()});
        b.push_back(it.first);
    }

    int bigger = 0;
    for (int j = 0; j < (int)szs.size(); j++) {
        auto x = szs[j];

        if (x.first > x.second) {
            bigger++;
            bigvec.push_back(b[j]);
        }
    }

    return bigger;
}

vector<int> res;
void solve (int i, int from = -1) {
    int c = calcBigger (i);
    if (!c) return;
    vis[i] = 1;

    if (from != -1)
        for (int j : mp[from][i]) res.push_back (j);

    for (int j : sids[i]) res.push_back (j);

    if (c > 1 && bigvec[0] == from) swap (bigvec[0], bigvec[1]);
    for (auto it : mp[i]) {
        if (it.first == from || it.first == bigvec[0]) continue;

        for (int j : it.second) res.push_back (j);
    }

    for (int j = 0; j < c; j++) {
        int v = bigvec[j];
        if (vis[v]) continue;

        solve (v, i);
    }
}

int main() {
    // ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int tc = 1;
    for(int cn = 1; cn <= tc; cn++) {
        scanf("%d%d", &n, &m);

        for (int i = 1; i <= n; i++) {
            int c; scanf("%d", &c);
            int a, b;

            scanf("%d", &a);
            ids[a].push_back(i);
            cnt[a]++;
            if (c == 1) sids[a].push_back(i);
            else {
                scanf("%d", &b);
                ids[b].push_back(i);
                cnt[b]++;

                mp[a][b].push_back (i);
                mp[b][a].push_back (i);
            }
        }

        vector<int> vec;
        for (int i = 1; i <= m; i++) {
            int bigger = calcBigger(i);

            if (bigger == 0) {
                for (auto x : ids[i]) res.push_back(x);
            }
            else if (bigger == 1) {
                vec.push_back(i);
            }
            else if (bigger > 2) {
                puts("-1");
                return 0;
            }
        }

        sort(vec.begin(), vec.end());
        for (auto i : vec) {
            if (vis[i]) continue;

            solve (i);
        }

        assert ((int)res.size() <= n);
        if ((int)res.size() != n)
            puts("-1");

        else {
            for (int i = 0; i < n; i++) {
                printf ("%d", res[i]);
                if (i == n - 1) printf ("\n");
                else printf(" ");
            }
        }
    }
    return 0;
}
Copy
Gym amr962
GNU G++17
30 ms
47.8 MB
Runtime Error