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;

vector<int> adj[N];
vector<int> ids[N];
int n, m, p[N];

int get (int a) {
    return p[a] = (a == p[a] ? a : get(p[a]));
}

bool join (int a, int b) {
    a = get(a), b = get(b);

    if (a == b) return false;

    p[b] = a;

    return true;
}

vector<int> res;
bool vis[N];

void dfs (int u) {
    res.push_back (u);
    vis[u] = true;

    for (int v : adj[u]) {
        if (vis[v]) continue;

        dfs(v);
    }
}

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++) {
            p[i] = i;
            int c; scanf("%d", &c);
            for (int j = 0; j < c; j++) {
                int x; scanf("%d", &x);
                ids[x].push_back(i);
            }
        }

        bool ok = true;
        for (int i = 1; i <= m; i++) {
            if (ids[i].empty()) continue;

            ok &= ((int)ids[i].size() < 3);
            int pre = ids[i][0];
            for (int j = 1; j < (int)ids[i].size(); j++) {
                ok &= join (pre, ids[i][j]);
                pre = ids[i][j];
            }
        }

        if (!ok) printf("-1");
        else {
            for (int i = 1; i <= m; i++) {
                if ((int)ids[i].size() < 2) continue;

                int u = ids[i][0];
                int v = ids[i][1];
                adj[u].push_back(v);
                adj[v].push_back(u);
            }

            for (int i = 1; i <= n; i++) {
                if (!vis[i] && (int)adj[i].size() <= 1) {
                    dfs (i);
                }
            }

            assert ((int)res.size() == n);
            for (int i = 0; i < n; i++) {
                printf("%d", res[i]);
                if (i != n - 1) printf(" ");
            }
        }
    }
    return 0;
}
Copy
Gym amr962
GNU G++17
14 ms
24.1 MB
Wrong Answer