#include <bits/stdc++.h>
#include "output_validators/validator/simulate.h"
using namespace std;

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;


int main() {
    int T;
    cin >> T;

    rep(_,0,T){
        int n = rand()%100+2;
        vector<vi> C(n, vi());
        vi rename(n);
        rep(i,0,n) rename[i] = i;
        random_shuffle(all(rename));
        rep(i,1,n){
            int p = rename[rand()%i];
            int c1 = rename[i];
            C[c1].push_back(p);
            C[p].push_back(c1);
        }
        for (auto& v : C) random_shuffle(all(v));
        vi P;
        rep(c1,0,n){
            P.push_back(c1);
        }
        random_shuffle(all(P));

        vi ans1 = simulate_slow(C,P);
        vi ans2 = simulate_fast(C,P);

        if(ans1 != ans2){
            cout << "Different answers:\n";
            trav(y,ans1){
                cout << y+1 << " ";
            }
            cout << "\nvs\n";
            trav(y,ans2){
                cout << y+1 << " ";
            }
            cout << "\nCase:\n";
            rep(c1,0,n){
                trav(y, C[c1]){
                    if(y < c1){
                        cout << y+1 << " " << c1+1 << "\n";
                    }
                }
            }
            trav(y, P){
                cout << y+1 << " ";
            }cout << "\n";
        }
    }

    return 0;
}