OIG XV - plo

// https://szkopul.edu.pl/problemset/problem/8l-VO_3t9ztnFSIngG3bYUot/site/?key=statement

#include <bits/stdc++.h>

using namespace std;

#define int long long

constexpr int sizik = 1000 * 1001;

#define ar std::array
#define pr std::pair
#define vec std::vector

typedef vec<vec<int>> _kra;

std::set<int, std::greater<int>> in[sizik], out[sizik];

bool chk1(const std::pair<int, int>& a, const std::pair<int, int>& b) {
    return a.first >= b.first;
}

ar<std::pair<int, int>, 2> check(int n) {
    std::set<std::pair<int, int>> s;
    for (int i = 1; i <= n; i++) {
        for (const auto& a : out[i]) {
            s.erase({i, a});
        }

        for (const auto& a : in[i]) {
            if (s.empty() || chk1(*s.begin(), {a, i}) || (*s.begin()).first == i)
                s.insert({a, i});
            else
                return {std::make_pair(a, i), *s.begin()};
        }
    }

    return {std::make_pair(-1, -1), std::make_pair(-1, -1)};
}

void solve() {
    int n;
    std::cin >> n;

    for (int i = 1; i <= n; i++) {
        in[i].clear();
        out[i].clear();
    }

    for (int i = 1; i <= n - 2; i++) {
        int a, b;
        std::cin >> a >> b;

        if (a > b) std::swap(a, b);
        in[a].insert(b);
        out[b].insert(a);
    }

    const auto p1 = check(n);
    in[p1[0].second].erase(p1[0].first);
    out[p1[0].first].erase(p1[0].second);
    const auto p2 = check(n);
    if (p2[0].second == -1) {
        std::cout << p1[0].second << " " << p1[0].first << '\n';
    } else {
        std::cout << p1[1].second << " " << p1[1].first << '\n';
    }
}

int32_t main() {
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);

    int t = 1;
    std::cin >> t;

    for (; t > 0; t--) {
        solve();
    }

    return 0;
}