1468M - Similar Sets - CodeForces Solution

//region template
#include <bits/stdc++.h>

#define GET_MACRO(_1, _2, _3, NAME, ...) NAME
#define rep(...)        GET_MACRO(__VA_ARGS__, repn, rep0)(__VA_ARGS__)
#define rep0(i, b)      for(int i = 0; i < (b); ++i)
#define repn(i, a, b)   for(int i = (a); i < (b); ++i)
#define trav(a, b)      for(auto& a : b)
#define all(a)          (a).begin(),(a).end()
#define endl            '\n'
#define sz(x)           ((int)(x).size())
#define tests           int ___;cin>>___;while(___--)

using namespace std;
using ll = int64_t;
using ld = long double;
using ul = uint64_t;
using vi = vector<int>;
using vl = vector<ll>;
using vvi = vector<vi>;
using vvl = vector<vl>;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using vpi = vector<pi>;

static constexpr int inf = (int) 1e9 + 5;
static constexpr ll infl = (ll) 1e18 + 5;
static mt19937 rng((uint32_t) chrono::duration_cast<chrono::nanoseconds>(
        chrono::high_resolution_clock::now().time_since_epoch()).count());
//endregion

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.precision(10);

    tests {
        int n;
        cin >> n;
        vvi a(n);
        map<int, int> c;
        rep(i, n) {
            int k;cin >> k;
            rep(j, k) {
                int x;cin >> x;
                if (!c.count(x))
                    c.insert({x, sz(c)});
                a[i].push_back(c[x]);
            }
            sort(all(a[i]));
        }
        const int b = 250;

        vector p(sz(c), vpi());

        rep(i,n) {
            if (sz(a[i]) < b) continue;
            vi occ(sz(c), 0);
            trav(k, a[i]) occ[k] = 1;
            rep(j,n) {
                if (i == j) continue;
                int cnt = 0;
                trav(k, a[j]) {
                    cnt += occ[k];
                }
                if (cnt > 1) {
                    cout << i+1 << ' ' << j+1 << endl;
                    goto next;
                }
            }
        }

        rep(i,n) {
            if (sz(a[i]) >= b) continue;
            rep(j, sz(a[i])) {
                rep(k, j+1, sz(a[i])) {
                    p[a[i][j]].emplace_back(a[i][k], i);
                }
            }
        }
        rep(i,sz(c)) {
            sort(all(p[i]));
            rep(j, sz(p[i])-1) {
                if (p[i][j].first == p[i][j+1].first) {
                    cout << p[i][j].second + 1 << ' ' << p[i][j+1].second + 1 << endl;
                    goto next;
                }
            }
        }


        cout << -1 << endl;
        next:;
    };

    return 0;
}