首先先将所有元素离散化。
设 \(m=\sum k_i\)，因为 \(n,m\) 同阶，所以下文均用 \(n\) 来表示。
考虑根号分治。
-
对于元素个数超过 \(\sqrt n\) 的序列，不难发现这样的序列至多只有 \(\sqrt n\) 个。对于每个序列，把它的元素存进桶中，然后枚举其它所有的序列来判断。这部分时间复杂度是 \(\mathcal O(n\sqrt n)\) 的。
-
对于元素个数不超过 \(\sqrt n\) 的序列，枚举这些序列的元素对 \((x,y)\)，并把它们存储下来，进行判断。对于 \(\sum_{k_i\lt \sqrt n}\frac{k_i\times (k_i-1)}{2}\)，不难发现最大也才 \(n\sqrt n\)，所以这部分的时间复杂度也是 \(\mathcal O(n\sqrt n)\) 的。
实现时候需要精细一点，否则可能会 MLE。
具体细节看代码。
Code：
#include <bits/stdc++.h>
using namespace std;
#define siz(a) a.size()
#define pb push_back
#define fi first
#define se second
typedef pair <int, int> pii;
const int N = 200005;
int T;
int n, m, cnt;
int vis[N];
vector <int> v, b, a[N];
vector <pii> vec[N];
void init() {
v.clear(), b.clear(), m = 0;
for (int i = 1; i <= n; ++i) a[i].resize(1);
}
void solve() {
scanf("%d", &n), init();
for (int i = 1; i <= n; ++i) {
scanf("%d", &a[i][0]), m += a[i][0], a[i].resize(a[i][0] + 1);
for (int j = 1; j <= a[i][0]; ++j) scanf("%d", &a[i][j]), b.pb(a[i][j]);
sort(++a[i].begin(), a[i].end());
}
m = sqrt(m) / 2, sort(b.begin(), b.end()), b.erase(unique(b.begin(), b.end()), b.end());
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= a[i][0]; ++j)
a[i][j] = lower_bound(b.begin(), b.end(), a[i][j]) - b.begin() + 1;
for (int i = 1; i <= n; ++i) {
if (a[i][0] > m) {
cnt = 0;
memset(vis + 1, 0, sizeof (int) * siz(b));
for (int j = 1; j <= a[i][0]; ++j) vis[a[i][j]] = 1;
for (int j = 1; j <= n; ++j) if (i != j) {
cnt = 0;
for (int k = 1; k <= a[j][0]; ++k) {
++vis[a[j][k]], cnt += (vis[a[j][k]] == 2);
if (cnt == 2) return printf("%d %d\n", i, j), void();
}
for (int k = 1; k <= a[j][0]; ++k) --vis[a[j][k]];
}
}
else v.pb(i);
}
memset(vis + 1, 0, sizeof (int) * siz(b));
for (int i = 1; i <= siz(b); ++i) vec[i].clear();
for (auto i : v)
for (int j = 1; j <= a[i][0]; ++j)
for (int k = j + 1; k <= a[i][0]; ++k)
vec[a[i][j]].pb(pii(a[i][k], i));
for (int i = 1; i <= siz(b); ++i) {
for (auto j : vec[i]) {
if (vis[j.fi]) return printf("%d %d\n", vis[j.fi], j.se), void();
vis[j.fi] = j.se;
}
for (auto j : vec[i]) vis[j.fi] = 0;
}
printf("%d\n", -1);
}
int main() {
scanf("%d", &T);
while (T--) solve();
return 0;
}