Source Code
#include <bits/stdc++.h>

using namespace std;

const int N = 5e5 + 100;

bool done[N];
vector <int> ans;
vector < pair<int, int> > G[N];

void rec(int i) {
	vector < pair<int, int> > temp;
	for (auto [to, idx] : G[i]) {
		if (temp.size() && temp[0].first == to)
			temp.push_back({to, idx});
		else if (to + 1 && done[to]) {
			cout << "-1\n";
			exit(0);
		}
		else if (to + 1 && G[to].size()) {
			if (temp.empty())
				temp.push_back({to, idx});
			else {
				cout << "-1\n";
				exit(0);
			}
		}
		else
			ans.push_back(idx);
	}

	for (auto [to, _] : G[i]) {
		if (temp.size() && temp[0].first == to)
			continue;
		G[to].clear();
		done[to] = true;
	}
	done[i] = true;
	G[i].clear();
	if (temp.size()) {
		for (auto [_, idx] : temp)
			ans.push_back(idx);

		rec(temp[0].first);
	}
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int n, m;	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		int x, a, b = -1;
		cin >> x >> a;

		if (x == 2)
			cin >> b;

		if (b + 1 && a > b)
			swap(a, b);

		G[a].push_back({b, i});
	}

	for (int i = 1; i <= m; i++)
		sort(G[i].begin(), G[i].end());

	vector <int> nodes, cnt(m + 1);
	for (int i = 1; i <= m; i++) {
		nodes.push_back(i);
	
		for (auto [x, y] : G[i])
			if (x + 1 && G[x].size())
				cnt[i]++;
	}

	random_shuffle(nodes.begin(), nodes.end());

	// sort(nodes.begin(), nodes.end(), [&](int& a, int& b) {
	// 	return cnt[a] < cnt[b];
	// });

	// if (m >= 3 && cnt[nodes[1]] < cnt[nodes.back()])
	// 	swap(nodes[1], nodes.back());

	for (int i : nodes) {
		if (G[i].empty())
			continue;
		rec(i);
	}

	for (int i = 0; i < ans.size(); i++) {
		if (i) cout << ' ';
		cout << ans[i];
	}
	cout << '\n';

	return 0;
}
Copy
Gym Bsher
GNU G++17
7 ms
12.5 MB
Wrong Answer