#include <bits/stdc++.h>
using namespace std;

constexpr int maxn = 2e5 + 10, mod = 1e9 + 7;

int n, v[maxn] = {}, prv[maxn] = {}, nxt[maxn] = {}, nr_triang[maxn] = {},
    hash_contrib[maxn] = {}, set_hash = 0, curr_free = 1;

unordered_map<unsigned long long, int> precalc;

bool found_sol = false;

array<int, 3> triangles[maxn];
map<array<int, 3>, int> tri_sol;

auto by_nr_triang = [](int x, int y){
    return make_pair(nr_triang[x], x) < make_pair(nr_triang[y], y);
};

set<int, decltype(by_nr_triang)> verts_by_nr_triang(by_nr_triang);

constexpr static array<int, 3> get_tri(int x, int y, int z){
    array<int, 3> ret = {x, y, z};
    sort(begin(ret), end(ret));
    return ret;
}

/* Modifca nr_triang safely */
static void change_nr_triang(initializer_list<int> xs, int delta){
    for(auto x : xs){
        verts_by_nr_triang.erase(x);
        nr_triang[x] += delta;
        verts_by_nr_triang.insert(x);
    }
}

/* Returneaza solutia la starea curenta (memoizat) */
static int solve();

/* Setez triunghiul prv[x], nxt[x], x la y, dupa aia elimin triunghiul
 * apoi rezolv */
static auto solve_after_set(int x, int y){
    if(!found_sol)
        tri_sol[get_tri(x, prv[x], nxt[x])] = y;

    int new_free = x == curr_free ? y : curr_free;
    swap(curr_free, new_free);
    set_hash = (set_hash + mod - hash_contrib[x]) % mod;
    verts_by_nr_triang.erase(x);
    nxt[prv[x]] = nxt[x], prv[nxt[x]] = prv[x];
    change_nr_triang({ prv[x], nxt[x] }, -1);

    auto ret = solve();

    change_nr_triang({ prv[x], nxt[x] }, 1);
    nxt[prv[x]] = prv[nxt[x]] = x;
    verts_by_nr_triang.insert(x);
    set_hash = (set_hash + hash_contrib[x]) % mod;
    swap(curr_free, new_free);
    return ret;
}

/* Returneaza solutia la starea curenta (nememoizat) */
static int _solve(){
    if(verts_by_nr_triang.size() < 3){
        found_sol = true;
        return 1;
    }

    for(auto v2 : verts_by_nr_triang)
        if(nr_triang[v2] > 1) break;
        else if(v2 == curr_free || v2 == n) continue;
        else return solve_after_set(v2, v2);
    return (solve_after_set(curr_free, prv[curr_free])
        + solve_after_set(curr_free, nxt[curr_free]))%mod;
}

static int solve(){
    const unsigned long long idx = set_hash + ((unsigned long long)curr_free << 32);
    if(precalc.find(idx) == end(precalc))
        return precalc[idx] = _solve();
    return precalc[idx];
}

void testcase() {
    cin >> n;
    for (int i = 0; i <= n; i ++) {
        v[i] = 0;
        prv[i] = 0;
        nxt[i] = 0;
        nr_triang[i] = 0;
        hash_contrib[i] = 0;
    }
    found_sol = false;
	set_hash = 0;
	curr_free = 1;
    tri_sol.clear();
    verts_by_nr_triang.clear();
    precalc.clear();
    
    
    for(int i = 1; i <= n; ++i) cin >> v[i];
    for(int i = 1; i < n; ++i) nxt[v[i]] = v[i + 1];
    for(int i = 2; i <= n; ++i) prv[v[i]] = v[i - 1];
    nxt[v[n]] = v[1];
    prv[v[1]] = v[n];

    for(int i = 1, x, y, z; i <= n - 2; ++i){
        cin >> x >> y >> z;
        triangles[i] = get_tri(x, y, z);
        ++nr_triang[x], ++nr_triang[y], ++nr_triang[z];
    }

    for(int i = 1; i <= n; ++i)
        verts_by_nr_triang.insert(i);
    
    hash_contrib[0] = 1;
    for(int i = 1; i <= n; ++i) hash_contrib[i] = (1ll * hash_contrib[i - 1] * 125234) % mod;
	 
	 int x = solve();
     for(int i = 1; i <= n - 2; ++i)
          cout << tri_sol[triangles[i]] << ' ';
     cout << '\n';
     cout << x << '\n';
}

signed main() {
	int t;
	cin >> t;
	while (t --) {
		testcase();
	}
	return 0;
}