#pragma GCC optimize("Ofast,unroll-loops,fast-math,inline-functions,reorder-functions,omit-frame-pointer,tree-vectorize") #include "bits/stdc++.h" using namespace std; #define rep(i,a,b) for(int i=(a); i<(b); ++i) #define all(x) x.begin(),x.end() #define sz(x) int(x.size()) typedef vector vi; typedef vector vvi; #include using namespace __gnu_pbds; const int N = 5e4; gp_hash_table mp[N*3]; int main(){ cin.tie(NULL),ios::sync_with_stdio(false); int n; cin >> n; vi coords1,coords2; coords1.reserve(N*2+10); coords2.reserve(N*2+10); vvi lists(n); for(auto& v : lists){ int k; cin >> k; v.resize(k); for(auto& x : v) { cin >> x; coords1.push_back(x); } } sort(all(coords1)); coords1.erase(unique(all(coords1)),end(coords1)); for(auto& v : lists) for(auto& x : v) x = lower_bound(all(coords1),x)-begin(coords1); /* preprocessing to remove super small nodes */ { vi cnt(sz(coords1)); for(auto& v : lists) for(auto& x : v) cnt[x]++; for(auto& v : lists){ vi nxt; nxt.reserve(sz(v)); for(auto x : v) if (cnt[x] >= 2) { nxt.push_back(x); coords2.push_back(x); } v = nxt; } sort(all(coords2)); coords2.erase(unique(all(coords2)),end(coords2)); for(auto& v : lists) for(auto& x : v) x = lower_bound(all(coords2),x)-begin(coords2); } /* build graph */ int m = sz(coords2); const int B = cbrt((n+m)/2); vvi adj(n + m), large(n+m), supl(n+m); rep(i,0,n){ for(auto to : lists[i]) { adj[n+to].push_back(i); adj[i].push_back(n+to); } }rep(i,0,n+m) if (sz(adj[i]) >= B) for(auto j : adj[i]) if (sz(adj[j]) >= B) large[i].push_back(j); // run algo auto print = [&](array ans) -> void { sort(all(ans)); cout << coords1[coords2[ans[2]-n]] << ' '; cout << coords1[coords2[ans[3]-n]] << ' '; cout << ans[0]+1 << ' ' << ans[1]+1 << '\n'; exit(0); }; auto add = [&](int u, int v, int mid) -> void { auto& cur = mp[u][v]; if (cur > 0 and cur != mid+1){ // we found sol! array ans = {u,v,mid,cur-1}; print(ans); } cur = mid+1; }; rep(i,0,n+m) { sort(all(adj[i])); const int ss = sz(adj[i]); if (ss < B) { // small cent rep(u,0,ss) rep(v,u+1,ss) add(adj[i][u],adj[i][v],i); }else{ // large trip int st = sz(large[i]); rep(u,0,st) rep(v,u+1,st) add(large[i][u],large[i][v],i); } } // SLL ears rep(i,0,n+m) if (sz(adj[i]) < B) for(auto mid : adj[i]) if (sz(adj[mid]) >= B) for(auto j : large[mid]) add(min(i,j),max(i,j),mid); cout << "impossible\n"; }