Problem: We guessed a permutation p consisting of n integers. The permutation of length n is the array of length n where each element from 1 to n appears exactly once. This permutation is a secret for you.

For each position r from 2 to n we chose some other index l (l < r) and gave you the segment p_l, p_{l + 1}, ..., p_r in sorted order (i.e. we rearranged the elements of this segment in a way that the elements of this segment are sorted). Thus, you are given exactly n-1 segments of the initial permutation but elements inside each segment are sorted. The segments are given to you in random order.

For example, if the secret permutation is p=[3, 1, 4, 6, 2, 5] then the possible given set of segments can be:

  * [2, 5, 6] 
  * [4, 6] 
  * [1, 3, 4] 
  * [1, 3] 
  * [1, 2, 4, 6] 



Your task is to find any suitable permutation (i.e. any permutation corresponding to the given input data). It is guaranteed that the input data corresponds to some permutation (i.e. such permutation exists).

You have to answer t independent test cases.

Input

The first line of the input contains one integer t (1 ≤ t ≤ 100) — the number of test cases. Then t test cases follow.

The first line of the test case contains one integer n (2 ≤ n ≤ 200) — the length of the permutation.

The next n-1 lines describe given segments.

The i-th line contains the description of the i-th segment. The line starts with the integer k_i (2 ≤ k_i ≤ n) — the length of the i-th segment. Then k_i integers follow. All integers in a line are distinct, sorted in ascending order, between 1 and n, inclusive.

It is guaranteed that the required p exists for each test case.

It is also guaranteed that the sum of n over all test cases does not exceed 200 (∑ n ≤ 200).

Output

For each test case, print the answer: n integers p_1, p_2, ..., p_n (1 ≤ p_i ≤ n, all p_i should be distinct) — any suitable permutation (i.e. any permutation corresponding to the test case input).

Example

Input


5
6
3 2 5 6
2 4 6
3 1 3 4
2 1 3
4 1 2 4 6
5
2 2 3
2 1 2
2 1 4
2 4 5
7
3 1 2 6
4 1 3 5 6
2 1 2
3 4 5 7
6 1 2 3 4 5 6
3 1 3 6
2
2 1 2
5
2 2 5
3 2 3 5
4 2 3 4 5
5 1 2 3 4 5


Output


3 1 4 6 2 5 
3 2 1 4 5 
2 1 6 3 5 4 7 
1 2 
2 5 3 4 1 

Solution (in JAVA):

Solution:
import java.io.*;
import java.util.*;

public class Solution {

    private static BufferedReader br;
    private static StreamTokenizer st;
    private static PrintWriter pw;

    static final int INF = 1000000007;
    static final int MOD = 998244353;

    static List<Integer> edges[];

    static void bfs(int r, int dst[]) {
        Queue<Integer> queue = new LinkedList<>();
        boolean vis[] = new boolean[dst.length];
        vis[r] = true;
        dst[r] = 0;
        queue.offer(r);
        while (!queue.isEmpty()) {
            int x = queue.size();
            while (x-- > 0) {
                int f = queue.poll();
                List<Integer> es = edges[f];
                for (int i = 0; i < es.size(); i++) {
                    int t = es.get(i);
                    if (vis[t]) {
                        continue;
                    }
                    vis[t] = true;
                    dst[t] = dst[f] + 1;
                    queue.offer(t);
                }
            }
        }
    }

    private static void solve() throws IOException {
        int tt = nextInt();
        for (int cs = 1; cs <= tt; cs++) {
            int n = nextInt();
            Set<Integer> cnt[] = new Set[n + 1];
            int a[][] = new int[n - 1][n + 1];
            for (int i = 1; i <= n; i++) {
                cnt[i] = new HashSet<>();
            }
            for (int i = 0; i < n - 1; i++) {
                a[i][0] = nextInt();
                for (int j = 1; j <= a[i][0]; j++) {
                    a[i][j] = nextInt();
                }
            }
            int res[] = new int[n + 1];
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    cnt[j].clear();
                }
                for (int k = 0; k < n - 1; k++) {
                    for (int j = 1; j <= a[k][0]; j++) {
                        cnt[a[k][j]].add(k);
                    }
                }
                int rear = -1;
                for (int j = 1; j <= n; j++) {
                    if (i == j) {
                        continue;
                    }
                    if (cnt[j].size() == 1) {
                        rear = j;
                        break;
                    }
                }
                if (rear == -1) {
                    continue;
                }
                res[1] = i;
                int idx = n;
                res[idx--] = rear;
                boolean ok = true;
                while (idx > 1) {
                    rear = -1;
                    for (int k : cnt[res[idx + 1]]) {
                        for (int j = 1; j <= n; j++) {
                            cnt[j].remove(k);
                        }
                    }
                    for (int j = 1; j <= n; j++) {
                        if (j == res[1]) {
                            continue;
                        }
                        if (cnt[j].size() == 1) {
                            rear = j;
                            break;
                        }
                    }
                    if (rear == -1) {
                        ok = false;
                        break;
                    }
                    res[idx--] = rear;
                }
                if (ok) {
                    int pos[] = new int[n + 1];
                    for (int j = 1; j <= n; j++) {
                        pos[res[j]] = j;
                    }
                    for (int j = 0; j < n - 1; j++) {
                        int min = n;
                        int max = 1;
                        for (int k = 1; k <= a[j][0]; k++) {
                            min = Math.min(min, pos[a[j][k]]);
                            max = Math.max(max, pos[a[j][k]]);
                        }
                        if (max - min + 1 != a[j][0]) {
                            ok = false;
                            break;
                        }
                    }
                }
                if (ok) {
                    break;
                }
            }
            for (int i = 1; i <= n; i++) {
                if (i > 1) {
                    pw.print(" ");
                }
                pw.print(res[i]);
            }

//            pw.format("Case #%d: %f", cs, 1.0 - del);
            if (cs < tt) {
                pw.println();
            }
        }
    }

    static void getDiv(Map<Integer, Integer> map, int n) {
        int sqrt = (int) Math.sqrt(n);
        for (int i = sqrt; i >= 2; i--) {
            if (n % i == 0) {
                getDiv(map, i);
                getDiv(map, n / i);
                return;
            }
        }
        map.put(n, map.getOrDefault(n, 0) + 1);
    }

    public static boolean[] generatePrime(int n) {
        boolean p[] = new boolean[n + 1];
        p[2] = true;

        for (int i = 3; i <= n; i += 2) {
            p[i] = true;
        }

        for (int i = 3; i <= Math.sqrt(n); i += 2) {
            if (!p[i]) {
                continue;
            }
            for (int j = i * i; j <= n; j += i << 1) {
                p[j] = false;
            }
        }
        return p;
    }

    static boolean isPrime(long n) { //determines if n is a prime number
        int p[] = {2, 3, 5, 233, 331};
        int pn = p.length;
        long s = 0, t = n - 1;//n - 1 = 2^s * t
        while ((t & 1) == 0) {
            t >>= 1;
            ++s;
        }
        for (int i = 0; i < pn; ++i) {
            if (n == p[i]) {
                return true;
            }
            long pt = pow(p[i], t, n);
            for (int j = 0; j < s; ++j) {
                long cur = llMod(pt, pt, n);
                if (cur == 1 && pt != 1 && pt != n - 1) {
                    return false;
                }
                pt = cur;
            }
            if (pt != 1) {
                return false;
            }
        }
        return true;
    }

    static long llMod(long a, long b, long mod) {
        return (a * b - (long) ((double) a / mod * b + 0.5) * mod + mod) % mod;
//        long r = 0;
//        a %= mod;
//        b %= mod;
//        while (b > 0) {
//            if ((b & 1) == 1) {
//                r = (r + a) % mod;
//            }
//            b >>= 1;
//            a = (a << 1) % mod;
//        }
//        return r;
    }

    static int pow(long a, long n) {
        long ans = 1;
        while (n > 0) {
            if ((n & 1) == 1) {
                ans = (ans * a) % MOD;
            }
            a = (a * a) % MOD;
            n >>= 1;
        }
        return (int) ans;
    }

    static int pow(long a, long n, long mod) {
        long ans = 1;
        while (n > 0) {
            if ((n & 1) == 1) {
                ans = llMod(ans, a, mod);
            }
            a = llMod(a, a, mod);
            n >>= 1;
        }
        return (int) ans;
    }

    private static long[][] initC(int n) {
        long c[][] = new long[n][n];

        for (int i = 0; i < n; i++) {
            c[i][0] = 1;
        }

        for (int i = 1; i < n; i++) {
            for (int j = 1; j <= i; j++) {
                c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
            }
        }
        return c;
    }

    /**
     * ps: n >= m, choose m from n;
     */
    private static int c(long n, long m) {
        if (m > n) {
            n ^= m;
            m ^= n;
            n ^= m;
        }
        m = Math.min(m, n - m);

        long top = 1;
        long bot = 1;
        for (long i = n - m + 1; i <= n; i++) {
            top = (top * i) % MOD;
        }
        for (int i = 1; i <= m; i++) {
            bot = (bot * i) % MOD;
        }

        return (int) ((top * pow(bot, MOD - 2)) % MOD);
    }

    static int gcd(int a, int b) {
        if (a < b) {
            a ^= b;
            b ^= a;
            a ^= b;
        }
        while (b != 0) {
            int tmp = a % b;
            a = b;
            b = tmp;
        }
        return a;
    }

    static boolean even(long n) {
        return (n & 1) == 0;
    }

    public static void main(String args[]) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        st = new StreamTokenizer(br);
        pw = new PrintWriter(new OutputStreamWriter(System.out));
        st.ordinaryChar('\'');
        st.ordinaryChar('\"');
        st.ordinaryChar('/');

        long t = System.currentTimeMillis();
        solve();
        pw.flush();
    }

    private static long[] anLong(int n) throws IOException {
        long a[] = new long[n];
        for (int i = 0; i < n; i++) {
            a[i] = nextInt();
        }
        return a;
    }

    private static String next(int len) throws IOException {
        char ch[] = new char[len];
        int cur = 0;
        char c;
        while ((c = (char) br.read()) == '\n' || c == '\r' || c == ' ' || c == '\t') ;
        do {
            ch[cur++] = c;
        } while (!((c = (char) br.read()) == '\n' || c == '\r' || c == ' ' || c == '\t'));
        return String.valueOf(ch, 0, cur);
    }

    private static int nextInt() throws IOException {
        st.nextToken();
        return (int) st.nval;
    }

    private static long nextLong() throws IOException {
        st.nextToken();
        return (long) st.nval;
//        return Long.parseLong(nextLine());
    }

    private static double nextDouble() throws IOException {
        st.nextToken();
        return st.nval;
    }

    private static String[] nextSS(String reg) throws IOException {
        return br.readLine().split(reg);
    }

    private static String nextLine() throws IOException {
        return br.readLine();
    }
}