#include <bits/stdc++.h>
using namespace std;
/*
Full program:
- Read bipartite graph: left 1..n (positions), right 1..n (values).
- Run Hopcroft-Karp to obtain an initial perfect matching (matchingL/matchingR).
- For i = 1..n: run BFS on alternating directed graph from left i to find reachable right nodes,
pick the smallest reachable value among adjL[i] (or keep current matched value if better),
reconstruct alternation path and flip edges along it, then ban left i and chosen right (so they are fixed).
- Output ans[1..n].
Input format:
n
k1 v11 v12 ... v1k1
k2 v21 v22 ... v2k2
...
kn vn1 vn2 ... vnk_n
*/
int n;
vector<vector<int>> adjL; // adjL[1..n]: list of possible values for left u
vector<int> matchingL; // matchingL[u] = matched value (0 if none)
vector<int> matchingR; // matchingR[v] = matched left (0 if none)
// Hopcroft-Karp implementation for left 1..n, right 1..n
struct HopcroftKarp {
int n;
vector<vector<int>> *adj;
vector<int> dist;
const int INF = 1e9;
HopcroftKarp(int n_, vector<vector<int>> *adj_) : n(n_), adj(adj_) {
dist.assign(n+1, 0);
}
bool bfs() {
queue<int> q;
for (int u = 1; u <= n; ++u) {
if (matchingL[u] == 0) {
dist[u] = 0;
q.push(u);
} else dist[u] = INF;
}
bool reachableFree = false;
while (!q.empty()) {
int u = q.front(); q.pop();
for (int v : (*adj)[u]) {
int u2 = matchingR[v];
if (u2 == 0) { // free on right: found potential augmenting path
reachableFree = true;
} else {
if (dist[u2] == INF) {
dist[u2] = dist[u] + 1;
q.push(u2);
}
}
}
}
return reachableFree;
}
bool dfs(int u) {
for (int v : (*adj)[u]) {
int u2 = matchingR[v];
if (u2 == 0 || (dist[u2] == dist[u] + 1 && dfs(u2))) {
matchingL[u] = v;
matchingR[v] = u;
return true;
}
}
dist[u] = INF;
return false;
}
int max_matching() {
fill(matchingL.begin(), matchingL.end(), 0);
fill(matchingR.begin(), matchingR.end(), 0);
int matching = 0;
while (bfs()) {
for (int u = 1; u <= n; ++u) {
if (matchingL[u] == 0) {
if (dfs(u)) matching++;
}
}
}
// Note: matching variable counts augmentations after BFS loops; but to ensure correct
// count, we can count matched lefts:
int cnt = 0;
for (int u = 1; u <= n; ++u) if (matchingL[u] != 0) ++cnt;
return cnt;
}
};
// Greedy BFS on alternating directed graph + flip
vector<int> ans;
vector<char> banL, banR;
int bfs_and_flip_choose_min(int start) {
// visited + parent arrays
vector<char> visL(n+1, 0), visR(n+1, 0);
vector<int> parentL(n+1, -1); // parentLeft[u] = right v
vector<int> parentR(n+1, -1); // parentRight[v] = left u
queue<int> q;
visL[start] = 1;
q.push(start);
// BFS on alternating graph (we queue left nodes)
while (!q.empty()) {
int u = q.front(); q.pop();
// traverse non-matching edges u -> v (skip edges that are matching edge of u)
for (int v : adjL[u]) {
if (banR[v]) continue;
if (matchingL[u] == v) continue; // matching edge oriented v->u, not u->v
if (visR[v]) continue;
visR[v] = 1;
parentR[v] = u;
int u2 = matchingR[v];
if (u2 != 0 && !banL[u2] && !visL[u2]) {
visL[u2] = 1;
parentL[u2] = v;
q.push(u2);
}
}
}
// pick smallest candidate in adjL[start] that is reachable (or the current matched value)
int curMatched = matchingL[start];
int pick = INT_MAX;
for (int v : adjL[start]) {
if (banR[v]) continue;
if (visR[v] || curMatched == v) {
if (v < pick) pick = v;
}
}
if (pick == INT_MAX) {
// theoretically shouldn't happen if initial matching is perfect
// fallback: if current matched value exists and not banned, pick it
if (curMatched != 0 && !banR[curMatched]) pick = curMatched;
else return -1;
}
// reconstruct and flip along alternation path from start to pick
int v = pick;
while (true) {
int u;
if (parentR[v] != -1) u = parentR[v];
else u = start; // if pick was the current matched value and parent not set
int oldv = matchingL[u];
matchingL[u] = v;
matchingR[v] = u;
if (u == start) break;
// move to the previous right on path
v = parentL[u];
if (v == -1) break; // defensive
}
// fix (ban) start and pick
banL[start] = 1;
banR[pick] = 1;
ans[start] = pick;
return pick;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
adjL.assign(n+1, {});
for (int i = 1; i <= n; ++i) {
int k; cin >> k;
adjL[i].resize(k);
for (int j = 0; j < k; ++j) cin >> adjL[i][j];
sort(adjL[i].begin(), adjL[i].end()); // sort so we can pick smallest quickly
}
matchingL.assign(n+1, 0);
matchingR.assign(n+1, 0);
HopcroftKarp hk(n, &adjL);
int matched = hk.max_matching();
// verify perfect matching
if (matched != n) {
cout << -1 << '\n';
return 0;
}
// prepare for greedy assignment
ans.assign(n+1, 0);
banL.assign(n+1, 0);
banR.assign(n+1, 0);
// Greedy for i = 1..n
for (int i = 1; i <= n; ++i) {
if (banL[i]) continue; // normally false
int chosen = bfs_and_flip_choose_min(i);
if (chosen == -1) {
cout << -1 << '\n';
return 0;
}
// Optionally clear adjL[i] to speed future iterations (i is banned)
// adjL[i].clear();
}
// output ans[1..n]
for (int i = 1; i <= n; ++i) {
if (i > 1) cout << ' ';
cout << ans[i];
}
cout << '\n';
return 0;
}
