#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