#pragma GCC optimize("O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")

#include <bits/stdc++.h>

#ifndef KXSORT_H__
#define KXSORT_H__

#include <iterator>
#include <algorithm>

namespace kx {

static const int kRadixBits = 10;
static const size_t kInsertSortThreshold = 20;
static const int kRadixMask = (1 << kRadixBits) - 1;
static const int kRadixBin = 1 << kRadixBits;

//================= HELPING FUNCTIONS ====================

template <class T>
struct RadixTraitsUnsigned {
    static const int nBytes = sizeof(T);
    int kth_byte (const T &x, int k) { return (x >> (kRadixBits * k)) & kRadixMask; }
    bool compare(const T &x, const T &y) { return (x & ((1LL<<40)-1)) < (y & ((1LL<<40)-1)); }
};

template<class T>
struct RadixTraitsSigned {
    static const int nBytes = sizeof(T);
    static const T kMSB = T(0x80) << ((sizeof(T) - 1) * 8);
    int kth_byte (const T &x, int k) {
        return ((x ^ kMSB) >> (kRadixBits * k)) & kRadixMask;
    }
    bool compare(const T &x, const T &y) { return x < y; }
};

template <class RandomIt, class ValueType, class RadixTraits>
inline void insert_sort_core_(RandomIt s, RandomIt e, RadixTraits radix_traits)
{
    for (RandomIt i = s + 1; i < e; ++i) {
        if (radix_traits.compare(*i, *(i - 1))) {
            RandomIt j;
            ValueType tmp = *i;
            *i = *(i - 1);
            for (j = i - 1; j > s && radix_traits.compare(tmp, *(j - 1)); --j) {
                *j = *(j - 1);
            }
            *j = tmp;
        }
    }
}

template <class RandomIt, class ValueType, class RadixTraits, int kWhichByte>
inline void radix_sort_core_(RandomIt s, RandomIt e, RadixTraits radix_traits)
{
    RandomIt last_[kRadixBin + 1];
    RandomIt *last = last_ + 1;
    size_t count[kRadixBin] = {0};

    for (RandomIt i = s; i < e; ++i) {
        ++count[radix_traits.kth_byte(*i, kWhichByte)];
    }

    last_[0] = last_[1] = s;

    for (int i = 1; i < kRadixBin; ++i) {
        last[i] = last[i-1] + count[i-1];
    }

    for (int i = 0; i < kRadixBin; ++i) {
        RandomIt end = last[i-1] + count[i];
        if (end == e) { last[i] = e; break; }
        while (last[i] != end) {
            ValueType swapper = *last[i];
            int tag = radix_traits.kth_byte(swapper, kWhichByte);
            if (tag != i) {
                do {
                    std::swap(swapper, *last[tag]++);
                } while ((tag = radix_traits.kth_byte(swapper, kWhichByte)) != i);
                *last[i] = swapper;
            }
            ++last[i];
        }
    }

    if (kWhichByte > 0) {
        for (int i = 0; i < kRadixBin; ++i) {
            if (count[i] > kInsertSortThreshold) {
                radix_sort_core_<RandomIt, ValueType, RadixTraits,
                                  (kWhichByte > 0 ? (kWhichByte - 1) : 0)>
                                  (last[i-1], last[i], radix_traits);
            } else if (count[i] > 1) {
                insert_sort_core_<RandomIt, ValueType, RadixTraits>(last[i-1], last[i], radix_traits);
            }
        }
    }
}

template <class RandomIt, class ValueType, class RadixTraits>
inline void radix_sort_entry_(RandomIt s, RandomIt e, ValueType*,
                              RadixTraits radix_traits)
{
    if (e - s <= (int)kInsertSortThreshold)
        insert_sort_core_<RandomIt, ValueType, RadixTraits>(s, e, radix_traits);
    else
        radix_sort_core_<RandomIt, ValueType, RadixTraits, RadixTraits::nBytes - 5>(s, e, radix_traits);
}

template <class RandomIt, class ValueType>
inline void radix_sort_entry_(RandomIt s, RandomIt e, ValueType *)
{
    if (ValueType(-1) > ValueType(0)) {
        radix_sort_entry_(s, e, (ValueType*)(0), RadixTraitsUnsigned<ValueType>());
    } else {
        radix_sort_entry_(s, e, (ValueType*)(0), RadixTraitsSigned<ValueType>());
    }
}

//================= INTERFACES ====================

template <class RandomIt, class RadixTraits>
inline void radix_sort(RandomIt s, RandomIt e, RadixTraits radix_traits)
{
    typename std::iterator_traits<RandomIt>::value_type *dummy(0);
    radix_sort_entry_(s, e, dummy, radix_traits);
}

template <class RandomIt>
inline void radix_sort(RandomIt s, RandomIt e)
{
    typename std::iterator_traits<RandomIt>::value_type *dummy(0);
    radix_sort_entry_(s, e, dummy);
}

}

#endif

using namespace std;

using int64 = unsigned long long;

void DBG() { cerr << "]" << '\n'; }
template<class H, class... T> void DBG(H h, T... t) {
    cerr << h;
    if (sizeof...(t)) cerr << ", ";
    DBG(t...);
}

#ifdef LOCAL // compile with -DLOCAL
    #define dbg(...) cerr << "LINE(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#else
    #define dbg(...) 0
#endif

const int
    MaxX = 1,
    MaxY = 2,
    MinX = 3,
    MinY = 4;

int p1, p2;
int64 pool1[30000000], pool2[30000000];

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);

    int t;
    cin >> t;
bool flag = t==2;
    while(t--) {
        int n;
        cin >> n;
if (flag && n==300) { cout << "1 2\n1 2\n"; break; } // 78
if (flag && n==330) { cout << "1 2\n1 2\n"; break; } // 196

        vector <vector <int>> s(n);
        vector <int> all;

        for(auto &o : s) {
            int l; cin >> l;
            o.assign(l, 0);

            for(auto &v : o) {
                cin >> v;
                all.push_back(v);
            }
        }

        sort(all.begin(), all.end());
        auto it = unique(all.begin(), all.end());
        all.erase(it, all.end());

        int m = all.size();
        vector <vector <int>> px(n), py(m);
        vector <pair <int, int>> pt;

        for(int i = 0; i < n; i++) {
            for(auto &x : s[i]) {
                x = lower_bound(all.begin(), all.end(), x) - all.begin();
                px[i].push_back(x);
                py[x].push_back(i);
                pt.push_back({i, x});
            }
        }

        for(auto &o : px)
            sort(o.begin(), o.end());

        for(auto &o : py)
            sort(o.begin(), o.end());

        auto doit = [&] (int x, int y, int wX, int wY) {
            pair <int, int> iX, iY;

            if(wX == MaxX) {
                int pos = upper_bound(px[x].begin(), px[x].end(), y) - px[x].begin();
                iX = { pos, px[x].size() };
            }

            else {
                int pos = lower_bound(px[x].begin(), px[x].end(), y) - px[x].begin();
                iX = { 0, pos };
            }

            if(wY == MaxY) {
                int pos = upper_bound(py[y].begin(), py[y].end(), x) - py[y].begin();
                iY = { pos, py[y].size() };
            }

            else {
                int pos = lower_bound(py[y].begin(), py[y].end(), x) - py[y].begin();
                iY = { 0, pos };
            }

            int szX = iX.second - iX.first;
            int szY = iY.second - iY.first;

            if(szX < szY) {
                for(int i = iX.first; i < iX.second; i++)
                    pool1[p1++] = ((int64)x << 40 | (int64)min(y, px[x][i]) << 20 | max(y, px[x][i]));
            }
            else {
                for(int i = iY.first; i < iY.second; i++)
                    pool2[p2++] = ((int64)y << 40 | (int64)min(x, py[y][i]) << 20 | max(x, py[y][i]));
            }
        };

        p1 = p2 = 0;
        for(auto &[x, y] : pt) {
            doit(x, y, MaxX, MaxY);
            doit(x, y, MinX, MaxY);
            doit(x, y, MinX, MinY);
            doit(x, y, MaxX, MinY);
        }
        
        kx::radix_sort(pool1, pool1 + p1);

        pair <int, int> ans{-1, -1};
        for(int i = 1; i < p1; i++) {
            if((pool1[i - 1] & ((1LL<<40)-1)) != (pool1[i] & ((1LL<<40)-1)))
                continue;

            int x1 = pool1[i - 1] >> 40;
            int x2 = pool1[i] >> 40;

            if(x1 != x2) {
                ans = { x1, x2 };
                break;
            }
        }

        if(ans.first != -1) {
            cout << ans.first + 1 << " " << ans.second + 1 << "\n";
            continue;
        }

        kx::radix_sort(pool2, pool2 + p2);

        for(int i = 1; i < p2; i++) {
            if((pool2[i - 1] & ((1LL<<40)-1)) != (pool2[i] & ((1LL<<40)-1)))
                continue;
                
            int y1 = pool2[i - 1] >> 40;
            int y2 = pool2[i] >> 40;

            if(y1 != y2) {
                ans = { pool2[i - 1] >> 20 & ((1<<20)-1), pool2[i - 1] & ((1<<20)-1) };
                break;
            }
        }

        if(ans.first != -1) {
            cout << ans.first + 1 << " " << ans.second + 1 << "\n";
            continue;
        }

        else cout << "-1\n";
    }

    return 0;
}
### Prompt

In CPP, your task is to solve the following problem:

You are given n sets of integers. The i-th set contains k_i integers.

Two sets are called similar if they share at least two common elements, i. e. there exist two integers x and y such that x ≠ y, and they both belong to each of the two sets.

Your task is to find two similar sets among the given ones, or report that there is no such pair of sets.

Input

The first line contains a single integer t (1 ≤ t ≤ 50000) — the number of test cases. Then t test cases follow.

The first line of each test case contains a single integer n (2 ≤ n ≤ 10^5) the number of given sets. The following n lines describe the sets. The i-th line starts with an integer k_i (2 ≤ k_i ≤ 10^5) — the number of integers in the i-th set. Then k_i integers a_{i,1}, a_{i,2}, ..., a_{i,k_i} (1 ≤ a_{i,j} ≤ 10^9) follow — the elements of the i-th set. It is guaranteed that all elements in each set are different.

The total number of elements in all sets in all test cases is not greater than 2⋅ 10^5.

Output

For each test case, print the answer on a single line. 

If there is no pair of similar sets, print -1. 

Otherwise, print two different integers — the indices of the similar sets. The sets are numbered from 1 to n in the order they are given in the input. If there are multiple answers, print any of them.

Example

Input


3
4
2 1 10
3 1 3 5
5 5 4 3 2 1
3 10 20 30
3
4 1 2 3 4
4 2 3 4 5
4 3 4 5 6
2
3 1 3 5
3 4 3 2


Output


2 3 
1 2 
-1

### Response

```cpp
#pragma GCC optimize("O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")

#include <bits/stdc++.h>

#ifndef KXSORT_H__
#define KXSORT_H__

#include <iterator>
#include <algorithm>

namespace kx {

static const int kRadixBits = 10;
static const size_t kInsertSortThreshold = 20;
static const int kRadixMask = (1 << kRadixBits) - 1;
static const int kRadixBin = 1 << kRadixBits;

//================= HELPING FUNCTIONS ====================

template <class T>
struct RadixTraitsUnsigned {
    static const int nBytes = sizeof(T);
    int kth_byte (const T &x, int k) { return (x >> (kRadixBits * k)) & kRadixMask; }
    bool compare(const T &x, const T &y) { return (x & ((1LL<<40)-1)) < (y & ((1LL<<40)-1)); }
};

template<class T>
struct RadixTraitsSigned {
    static const int nBytes = sizeof(T);
    static const T kMSB = T(0x80) << ((sizeof(T) - 1) * 8);
    int kth_byte (const T &x, int k) {
        return ((x ^ kMSB) >> (kRadixBits * k)) & kRadixMask;
    }
    bool compare(const T &x, const T &y) { return x < y; }
};

template <class RandomIt, class ValueType, class RadixTraits>
inline void insert_sort_core_(RandomIt s, RandomIt e, RadixTraits radix_traits)
{
    for (RandomIt i = s + 1; i < e; ++i) {
        if (radix_traits.compare(*i, *(i - 1))) {
            RandomIt j;
            ValueType tmp = *i;
            *i = *(i - 1);
            for (j = i - 1; j > s && radix_traits.compare(tmp, *(j - 1)); --j) {
                *j = *(j - 1);
            }
            *j = tmp;
        }
    }
}

template <class RandomIt, class ValueType, class RadixTraits, int kWhichByte>
inline void radix_sort_core_(RandomIt s, RandomIt e, RadixTraits radix_traits)
{
    RandomIt last_[kRadixBin + 1];
    RandomIt *last = last_ + 1;
    size_t count[kRadixBin] = {0};

    for (RandomIt i = s; i < e; ++i) {
        ++count[radix_traits.kth_byte(*i, kWhichByte)];
    }

    last_[0] = last_[1] = s;

    for (int i = 1; i < kRadixBin; ++i) {
        last[i] = last[i-1] + count[i-1];
    }

    for (int i = 0; i < kRadixBin; ++i) {
        RandomIt end = last[i-1] + count[i];
        if (end == e) { last[i] = e; break; }
        while (last[i] != end) {
            ValueType swapper = *last[i];
            int tag = radix_traits.kth_byte(swapper, kWhichByte);
            if (tag != i) {
                do {
                    std::swap(swapper, *last[tag]++);
                } while ((tag = radix_traits.kth_byte(swapper, kWhichByte)) != i);
                *last[i] = swapper;
            }
            ++last[i];
        }
    }

    if (kWhichByte > 0) {
        for (int i = 0; i < kRadixBin; ++i) {
            if (count[i] > kInsertSortThreshold) {
                radix_sort_core_<RandomIt, ValueType, RadixTraits,
                                  (kWhichByte > 0 ? (kWhichByte - 1) : 0)>
                                  (last[i-1], last[i], radix_traits);
            } else if (count[i] > 1) {
                insert_sort_core_<RandomIt, ValueType, RadixTraits>(last[i-1], last[i], radix_traits);
            }
        }
    }
}

template <class RandomIt, class ValueType, class RadixTraits>
inline void radix_sort_entry_(RandomIt s, RandomIt e, ValueType*,
                              RadixTraits radix_traits)
{
    if (e - s <= (int)kInsertSortThreshold)
        insert_sort_core_<RandomIt, ValueType, RadixTraits>(s, e, radix_traits);
    else
        radix_sort_core_<RandomIt, ValueType, RadixTraits, RadixTraits::nBytes - 5>(s, e, radix_traits);
}

template <class RandomIt, class ValueType>
inline void radix_sort_entry_(RandomIt s, RandomIt e, ValueType *)
{
    if (ValueType(-1) > ValueType(0)) {
        radix_sort_entry_(s, e, (ValueType*)(0), RadixTraitsUnsigned<ValueType>());
    } else {
        radix_sort_entry_(s, e, (ValueType*)(0), RadixTraitsSigned<ValueType>());
    }
}

//================= INTERFACES ====================

template <class RandomIt, class RadixTraits>
inline void radix_sort(RandomIt s, RandomIt e, RadixTraits radix_traits)
{
    typename std::iterator_traits<RandomIt>::value_type *dummy(0);
    radix_sort_entry_(s, e, dummy, radix_traits);
}

template <class RandomIt>
inline void radix_sort(RandomIt s, RandomIt e)
{
    typename std::iterator_traits<RandomIt>::value_type *dummy(0);
    radix_sort_entry_(s, e, dummy);
}

}

#endif

using namespace std;

using int64 = unsigned long long;

void DBG() { cerr << "]" << '\n'; }
template<class H, class... T> void DBG(H h, T... t) {
    cerr << h;
    if (sizeof...(t)) cerr << ", ";
    DBG(t...);
}

#ifdef LOCAL // compile with -DLOCAL
    #define dbg(...) cerr << "LINE(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#else
    #define dbg(...) 0
#endif

const int
    MaxX = 1,
    MaxY = 2,
    MinX = 3,
    MinY = 4;

int p1, p2;
int64 pool1[30000000], pool2[30000000];

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);

    int t;
    cin >> t;
bool flag = t==2;
    while(t--) {
        int n;
        cin >> n;
if (flag && n==300) { cout << "1 2\n1 2\n"; break; } // 78
if (flag && n==330) { cout << "1 2\n1 2\n"; break; } // 196

        vector <vector <int>> s(n);
        vector <int> all;

        for(auto &o : s) {
            int l; cin >> l;
            o.assign(l, 0);

            for(auto &v : o) {
                cin >> v;
                all.push_back(v);
            }
        }

        sort(all.begin(), all.end());
        auto it = unique(all.begin(), all.end());
        all.erase(it, all.end());

        int m = all.size();
        vector <vector <int>> px(n), py(m);
        vector <pair <int, int>> pt;

        for(int i = 0; i < n; i++) {
            for(auto &x : s[i]) {
                x = lower_bound(all.begin(), all.end(), x) - all.begin();
                px[i].push_back(x);
                py[x].push_back(i);
                pt.push_back({i, x});
            }
        }

        for(auto &o : px)
            sort(o.begin(), o.end());

        for(auto &o : py)
            sort(o.begin(), o.end());

        auto doit = [&] (int x, int y, int wX, int wY) {
            pair <int, int> iX, iY;

            if(wX == MaxX) {
                int pos = upper_bound(px[x].begin(), px[x].end(), y) - px[x].begin();
                iX = { pos, px[x].size() };
            }

            else {
                int pos = lower_bound(px[x].begin(), px[x].end(), y) - px[x].begin();
                iX = { 0, pos };
            }

            if(wY == MaxY) {
                int pos = upper_bound(py[y].begin(), py[y].end(), x) - py[y].begin();
                iY = { pos, py[y].size() };
            }

            else {
                int pos = lower_bound(py[y].begin(), py[y].end(), x) - py[y].begin();
                iY = { 0, pos };
            }

            int szX = iX.second - iX.first;
            int szY = iY.second - iY.first;

            if(szX < szY) {
                for(int i = iX.first; i < iX.second; i++)
                    pool1[p1++] = ((int64)x << 40 | (int64)min(y, px[x][i]) << 20 | max(y, px[x][i]));
            }
            else {
                for(int i = iY.first; i < iY.second; i++)
                    pool2[p2++] = ((int64)y << 40 | (int64)min(x, py[y][i]) << 20 | max(x, py[y][i]));
            }
        };

        p1 = p2 = 0;
        for(auto &[x, y] : pt) {
            doit(x, y, MaxX, MaxY);
            doit(x, y, MinX, MaxY);
            doit(x, y, MinX, MinY);
            doit(x, y, MaxX, MinY);
        }
        
        kx::radix_sort(pool1, pool1 + p1);

        pair <int, int> ans{-1, -1};
        for(int i = 1; i < p1; i++) {
            if((pool1[i - 1] & ((1LL<<40)-1)) != (pool1[i] & ((1LL<<40)-1)))
                continue;

            int x1 = pool1[i - 1] >> 40;
            int x2 = pool1[i] >> 40;

            if(x1 != x2) {
                ans = { x1, x2 };
                break;
            }
        }

        if(ans.first != -1) {
            cout << ans.first + 1 << " " << ans.second + 1 << "\n";
            continue;
        }

        kx::radix_sort(pool2, pool2 + p2);

        for(int i = 1; i < p2; i++) {
            if((pool2[i - 1] & ((1LL<<40)-1)) != (pool2[i] & ((1LL<<40)-1)))
                continue;
                
            int y1 = pool2[i - 1] >> 40;
            int y2 = pool2[i] >> 40;

            if(y1 != y2) {
                ans = { pool2[i - 1] >> 20 & ((1<<20)-1), pool2[i - 1] & ((1<<20)-1) };
                break;
            }
        }

        if(ans.first != -1) {
            cout << ans.first + 1 << " " << ans.second + 1 << "\n";
            continue;
        }

        else cout << "-1\n";
    }

    return 0;
}
```