#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x),end(x)
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; }
#define debug(a) cerr << "(" << #a << ": " << a << ")\n";
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pi;
const int mxN = 1e5+1, oo = 1e9;
map<string,int> artistmap;
typedef array<char,4> state;
unordered_map<ull,char> from[2][100];
vector<state> states[2][100];
vi adj[2][100];
int a[100];
ull getid(const state& s) {
ull res=0;
for(int i=0;i<4;++i) res|=((ull)s[i])<<(i*8);
return res;
}
void dfs(state s, int at, int d=0, bool rev=false) {
if(d==4) return;
s[0] = a[at];
sort(all(s));
auto id = getid(s);
for(int to : adj[rev][at]) {
if(find(all(s),a[to])==s.end()) {
if(!from[rev][to].count(id)) {
if(d==3) states[rev][to].push_back(s);
from[rev][to][id]=at;
dfs(s,to,d+1,rev);
}
}
}
}
void reconstruct(state s, int at, bool rev=false) {
vi ans;
for(int i=0;i<4;++i) {
int fr = from[rev][at][getid(s)];
for(int j=0;j<4;++j) if(s[j]==a[fr]) s[j]=0;
sort(all(s));
ans.push_back(fr+1);
at=fr;
}
if(!rev) reverse(all(ans));
cout << ans;
}
int main() {
int n; cin >> n;
for(int i=0;i<n;++i) {
string s; cin >> s;
if(!artistmap.count(s)) artistmap[s]=artistmap.size()+1;
a[i]=artistmap[s];
int k; cin >> k;
for(int j=0;j<k;++j) {
int to; cin >> to,to--;
if(a[to]!=a[i]) {
adj[0][i].push_back(to);
adj[1][to].push_back(i);
}
}
}
for(int i=0;i<n;++i) {
dfs({}, i);
dfs({},i,0,true);
}
vi order(n); iota(all(order),0);
random_shuffle(all(order));
for(int i:order) {
unordered_map<ull,int> cnt;
int total=states[0][i].size();
cnt.reserve(total*3);
for(auto s : states[0][i]) {
for(int j=0;j<16;++j) {
auto ss = s;
for(int k=0;k<4;++k) if(j&(1<<k)) {
ss[k]=0;
}
sort(all(ss));
cnt[getid(ss)]++;
}
}
for(auto s : states[1][i]) {
int cur = total;
for(int j=0;j<15;++j) {
auto ss = s;
int odd=0;
for(int k=0;k<4;++k) if(j&(1<<k)) {
ss[k]=0;
odd^=1;
}
sort(all(ss));
// inclusion exclusion
cur+=(1-2*odd)*cnt[getid(ss)];
}
if(cur) {
for(auto t : states[0][i]) {
bool found=true;
for(auto c : s) for(auto cc : t) if(c==cc) {
found=false;
break;
}
if(!found) continue;
reconstruct(t,i);
cout << ' ' << i+1 << ' ';
reconstruct(s,i,true);
cout << '\n';
exit(0);
}
assert(false);
}
}
}
cout << "fail\n";
}
I2luY2x1ZGUgImJpdHMvc3RkYysrLmgiCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CiNkZWZpbmUgYWxsKHgpIGJlZ2luKHgpLGVuZCh4KQp0ZW1wbGF0ZTx0eXBlbmFtZSBBLCB0eXBlbmFtZSBCPiBvc3RyZWFtJiBvcGVyYXRvcjw8KG9zdHJlYW0gJm9zLCBjb25zdCBwYWlyPEEsIEI+ICZwKSB7IHJldHVybiBvcyA8PCAnKCcgPDwgcC5maXJzdCA8PCAiLCAiIDw8IHAuc2Vjb25kIDw8ICcpJzsgfQp0ZW1wbGF0ZTx0eXBlbmFtZSBUX2NvbnRhaW5lciwgdHlwZW5hbWUgVCA9IHR5cGVuYW1lIGVuYWJsZV9pZjwhaXNfc2FtZTxUX2NvbnRhaW5lciwgc3RyaW5nPjo6dmFsdWUsIHR5cGVuYW1lIFRfY29udGFpbmVyOjp2YWx1ZV90eXBlPjo6dHlwZT4gb3N0cmVhbSYgb3BlcmF0b3I8PChvc3RyZWFtICZvcywgY29uc3QgVF9jb250YWluZXIgJnYpIHsgc3RyaW5nIHNlcDsgZm9yIChjb25zdCBUICZ4IDogdikgb3MgPDwgc2VwIDw8IHgsIHNlcCA9ICIgIjsgcmV0dXJuIG9zOyB9CiNkZWZpbmUgZGVidWcoYSkgY2VyciA8PCAiKCIgPDwgI2EgPDwgIjogIiA8PCBhIDw8ICIpXG4iOwp0eXBlZGVmIGxvbmcgbG9uZyBsbDsKdHlwZWRlZiB1bnNpZ25lZCBsb25nIGxvbmcgdWxsOwp0eXBlZGVmIHZlY3RvcjxpbnQ+IHZpOwp0eXBlZGVmIHZlY3Rvcjx2aT4gdnZpOwp0eXBlZGVmIHBhaXI8aW50LGludD4gcGk7CmNvbnN0IGludCBteE4gPSAxZTUrMSwgb28gPSAxZTk7Cm1hcDxzdHJpbmcsaW50PiBhcnRpc3RtYXA7CnR5cGVkZWYgYXJyYXk8Y2hhciw0PiBzdGF0ZTsKdW5vcmRlcmVkX21hcDx1bGwsY2hhcj4gZnJvbVsyXVsxMDBdOwp2ZWN0b3I8c3RhdGU+IHN0YXRlc1syXVsxMDBdOwp2aSBhZGpbMl1bMTAwXTsKaW50IGFbMTAwXTsKdWxsIGdldGlkKGNvbnN0IHN0YXRlJiBzKSB7CiAgICB1bGwgcmVzPTA7CiAgICBmb3IoaW50IGk9MDtpPDQ7KytpKSByZXN8PSgodWxsKXNbaV0pPDwoaSo4KTsKICAgIHJldHVybiByZXM7Cn0Kdm9pZCBkZnMoc3RhdGUgcywgaW50IGF0LCBpbnQgZD0wLCBib29sIHJldj1mYWxzZSkgewogICAgaWYoZD09NCkgcmV0dXJuOwogICAgc1swXSA9IGFbYXRdOwogICAgc29ydChhbGwocykpOwogICAgYXV0byBpZCA9IGdldGlkKHMpOwogICAgZm9yKGludCB0byA6IGFkaltyZXZdW2F0XSkgewogICAgICAgIGlmKGZpbmQoYWxsKHMpLGFbdG9dKT09cy5lbmQoKSkgewogICAgICAgICAgICBpZighZnJvbVtyZXZdW3RvXS5jb3VudChpZCkpIHsKICAgICAgICAgICAgICAgIGlmKGQ9PTMpIHN0YXRlc1tyZXZdW3RvXS5wdXNoX2JhY2socyk7CiAgICAgICAgICAgICAgICBmcm9tW3Jldl1bdG9dW2lkXT1hdDsKICAgICAgICAgICAgICAgIGRmcyhzLHRvLGQrMSxyZXYpOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgfQp9CnZvaWQgcmVjb25zdHJ1Y3Qoc3RhdGUgcywgaW50IGF0LCBib29sIHJldj1mYWxzZSkgewogICAgdmkgYW5zOwogICAgZm9yKGludCBpPTA7aTw0OysraSkgewogICAgICAgIGludCBmciA9IGZyb21bcmV2XVthdF1bZ2V0aWQocyldOwogICAgICAgIGZvcihpbnQgaj0wO2o8NDsrK2opIGlmKHNbal09PWFbZnJdKSBzW2pdPTA7CiAgICAgICAgc29ydChhbGwocykpOwogICAgICAgIGFucy5wdXNoX2JhY2soZnIrMSk7CiAgICAgICAgYXQ9ZnI7CiAgICB9CiAgICBpZighcmV2KSByZXZlcnNlKGFsbChhbnMpKTsKICAgIGNvdXQgPDwgYW5zOwp9CmludCBtYWluKCkgewogICAgaW50IG47IGNpbiA+PiBuOwogICAgZm9yKGludCBpPTA7aTxuOysraSkgewogICAgICAgIHN0cmluZyBzOyBjaW4gPj4gczsKICAgICAgICBpZighYXJ0aXN0bWFwLmNvdW50KHMpKSBhcnRpc3RtYXBbc109YXJ0aXN0bWFwLnNpemUoKSsxOwogICAgICAgIGFbaV09YXJ0aXN0bWFwW3NdOwogICAgICAgIGludCBrOyBjaW4gPj4gazsKICAgICAgICBmb3IoaW50IGo9MDtqPGs7KytqKSB7CiAgICAgICAgICAgIGludCB0bzsgY2luID4+IHRvLHRvLS07CiAgICAgICAgICAgIGlmKGFbdG9dIT1hW2ldKSB7CiAgICAgICAgICAgICAgICBhZGpbMF1baV0ucHVzaF9iYWNrKHRvKTsKICAgICAgICAgICAgICAgIGFkalsxXVt0b10ucHVzaF9iYWNrKGkpOwogICAgICAgICAgICB9CiAgICAgICAgfSAKICAgIH0KICAgIGZvcihpbnQgaT0wO2k8bjsrK2kpIHsKICAgICAgICBkZnMoe30sIGkpOwogICAgICAgIGRmcyh7fSxpLDAsdHJ1ZSk7CiAgICB9CiAgICB2aSBvcmRlcihuKTsgaW90YShhbGwob3JkZXIpLDApOwogICAgcmFuZG9tX3NodWZmbGUoYWxsKG9yZGVyKSk7CiAgICBmb3IoaW50IGk6b3JkZXIpIHsKICAgICAgICB1bm9yZGVyZWRfbWFwPHVsbCxpbnQ+IGNudDsKICAgICAgICBpbnQgdG90YWw9c3RhdGVzWzBdW2ldLnNpemUoKTsKICAgICAgICBjbnQucmVzZXJ2ZSh0b3RhbCozKTsKICAgICAgICBmb3IoYXV0byBzIDogc3RhdGVzWzBdW2ldKSB7CiAgICAgICAgICAgIGZvcihpbnQgaj0wO2o8MTY7KytqKSB7CiAgICAgICAgICAgICAgICBhdXRvIHNzID0gczsKICAgICAgICAgICAgICAgIGZvcihpbnQgaz0wO2s8NDsrK2spIGlmKGomKDE8PGspKSB7CiAgICAgICAgICAgICAgICAgICAgc3Nba109MDsKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgIHNvcnQoYWxsKHNzKSk7CiAgICAgICAgICAgICAgICBjbnRbZ2V0aWQoc3MpXSsrOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgICAgIGZvcihhdXRvIHMgOiBzdGF0ZXNbMV1baV0pIHsKICAgICAgICAgICAgaW50IGN1ciA9IHRvdGFsOwogICAgICAgICAgICBmb3IoaW50IGo9MDtqPDE1OysraikgewogICAgICAgICAgICAgICAgYXV0byBzcyA9IHM7CiAgICAgICAgICAgICAgICBpbnQgb2RkPTA7CiAgICAgICAgICAgICAgICBmb3IoaW50IGs9MDtrPDQ7KytrKSBpZihqJigxPDxrKSkgewogICAgICAgICAgICAgICAgICAgIHNzW2tdPTA7CiAgICAgICAgICAgICAgICAgICAgb2RkXj0xOwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgc29ydChhbGwoc3MpKTsKICAgICAgICAgICAgICAgIC8vIGluY2x1c2lvbiBleGNsdXNpb24KICAgICAgICAgICAgICAgIGN1cis9KDEtMipvZGQpKmNudFtnZXRpZChzcyldOwogICAgICAgICAgICB9CiAgICAgICAgICAgIGlmKGN1cikgewogICAgICAgICAgICAgICAgZm9yKGF1dG8gdCA6IHN0YXRlc1swXVtpXSkgewogICAgICAgICAgICAgICAgICAgIGJvb2wgZm91bmQ9dHJ1ZTsKICAgICAgICAgICAgICAgICAgICBmb3IoYXV0byBjIDogcykgZm9yKGF1dG8gY2MgOiB0KSBpZihjPT1jYykgewogICAgICAgICAgICAgICAgICAgICAgICBmb3VuZD1mYWxzZTsKICAgICAgICAgICAgICAgICAgICAgICAgYnJlYWs7CiAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgICAgIGlmKCFmb3VuZCkgY29udGludWU7CiAgICAgICAgICAgICAgICAgICAgcmVjb25zdHJ1Y3QodCxpKTsKICAgICAgICAgICAgICAgICAgICBjb3V0IDw8ICcgJyA8PCBpKzEgPDwgJyAnOwogICAgICAgICAgICAgICAgICAgIHJlY29uc3RydWN0KHMsaSx0cnVlKTsKICAgICAgICAgICAgICAgICAgICBjb3V0IDw8ICdcbic7CiAgICAgICAgICAgICAgICAgICAgZXhpdCgwKTsKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgIGFzc2VydChmYWxzZSk7CiAgICAgICAgICAgIH0KCiAgICAgICAgfQogICAgfQogICAgY291dCA8PCAiZmFpbFxuIjsKfQ==