Problem: Fishing Prince loves trees, and he especially loves trees with only one centroid. The tree is a connected graph without cycles.

A vertex is a centroid of a tree only when you cut this vertex (remove it and remove all edges from this vertex), the size of the largest connected component of the remaining graph is the smallest possible.

For example, the centroid of the following tree is 2, because when you cut it, the size of the largest connected component of the remaining graph is 2 and it can't be smaller.

<image>

However, in some trees, there might be more than one centroid, for example:

<image>

Both vertex 1 and vertex 2 are centroids because the size of the largest connected component is 3 after cutting each of them.

Now Fishing Prince has a tree. He should cut one edge of the tree (it means to remove the edge). After that, he should add one edge. The resulting graph after these two operations should be a tree. He can add the edge that he cut.

He wants the centroid of the resulting tree to be unique. Help him and find any possible way to make the operations. It can be proved, that at least one such way always exists.

Input

The input consists of multiple test cases. The first line contains an integer t (1≤ t≤ 10^4) — the number of test cases. The description of the test cases follows.

The first line of each test case contains an integer n (3≤ n≤ 10^5) — the number of vertices.

Each of the next n-1 lines contains two integers x, y (1≤ x,y≤ n). It means, that there exists an edge connecting vertices x and y.

It's guaranteed that the given graph is a tree.

It's guaranteed that the sum of n for all test cases does not exceed 10^5.

Output

For each test case, print two lines.

In the first line print two integers x_1, y_1 (1 ≤ x_1, y_1 ≤ n), which means you cut the edge between vertices x_1 and y_1. There should exist edge connecting vertices x_1 and y_1.

In the second line print two integers x_2, y_2 (1 ≤ x_2, y_2 ≤ n), which means you add the edge between vertices x_2 and y_2.

The graph after these two operations should be a tree.

If there are multiple solutions you can print any.

Example

Input


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


Output


1 2
1 2
1 3
2 3

Note

Note that you can add the same edge that you cut.

In the first test case, after cutting and adding the same edge, the vertex 2 is still the only centroid.

In the second test case, the vertex 2 becomes the only centroid after cutting the edge between vertices 1 and 3 and adding the edge between vertices 2 and 3.

Solution (in JAVA):

Solution:
//package cf670;

import java.io.*;
import java.util.*;
import java.util.stream.Collectors;

public class C {
    static boolean CONSTRUCTIVE = true;
    static long MOD = (long) 1e9 + 7;
    static long BIG = (long) 2e9;
    static int n;
    static int bestCut;
    static List<Node> centroids;

    public static void solve(Reader in, PrintWriter out) {
        n = in.nextInt();
        bestCut = Integer.MAX_VALUE;
        centroids = new ArrayList<>();
        Node[] tree = construct(n, in); // tree[0] == null, tree[1] is the root
        tree[1].minCutSize();
        if (centroids.size() > 1) {
            Node centroid = centroids.get(0);
            if (n - centroid.size == bestCut) {
                if (centroid.parent == null) throw new IllegalStateException();
                Node leaf = centroid.parent.findLeaf(centroid);
                out.println(leaf.id + " " + leaf.parent.id);
                out.println(leaf.id + " " + centroid.id);
            } else {
                for (Node child : centroid.children) {
                    if (child.size == bestCut) {
                        Node leaf = child.findLeaf(null);
                        out.println(leaf.id + " " + leaf.parent.id);
                        out.println(leaf.id + " " + centroid.id);
                        break;
                    }
                }
            }
        } else {
            Node leaf = tree[1].findLeaf(null);
            out.println(leaf.id + " " + leaf.parent.id);
            out.println(leaf.id + " " + leaf.parent.id);
        }
    }

    public static void main(String[] args) throws IOException {
        Reader in = null;
        PrintWriter out = null;
        for (String arg : args) {
            if (arg.startsWith("input")) {
                in = new Reader(arg);
            } else if (arg.startsWith("output")) {
                out = new PrintWriter(new FileWriter(arg));
            }
        }
        if (in == null) in = new Reader();
        if (out == null) out = new PrintWriter(new OutputStreamWriter(System.out));

        int tests = in.nextInt();
        for (int t = 0; t < tests; t++) {
            solve(in, out);
        }

        out.flush();
    }

    static class Node {
        int id;
        Node parent;
        SortedSet<Node> children;
        int depth;
        int size;

        public Node(int id) {
            this.id = id;
            this.children = new TreeSet<>(Comparator.comparingInt(v->v.id));
        }

        void construct(Node parent) {
            this.parent = parent;
            if (parent == null) {
                depth = 0;
            } else {
                depth = 1 + parent.depth;
                children.remove(parent);
            }
            int size = 1;
            for (Node child : children) {
                child.construct(this);
                size += child.size;
            }
            this.size = size;
        }

        void minCutSize() {
            int cutSize = cutSize();
            if (cutSize < bestCut) {
                bestCut = cutSize;
                centroids = new ArrayList<>();
                centroids.add(this);
            } else if (cutSize == bestCut) {
                centroids.add(this);
            }
            for (Node child : children) {
                child.minCutSize();
            }
        }

        Node findLeaf(Node avoid) {
            if (children.isEmpty()) {
                if (this == avoid) throw new IllegalStateException();
                return this;
            }
            for (Node child : children) {
                if (avoid == null || child.id != avoid.id) return child.findLeaf(avoid);
            }
            throw new IllegalStateException();
        }

        int cutSize() {
            int max = 0;
            for (Node child : children) {
                max = Math.max(child.size, max);
            }
            max = Math.max(max, n - size);
            return max;
        }
    }

    // constructs a tree with n nodes, rooted at 1
    static Node[] construct(int n, Reader in) {
        Node[] arr = new Node[n+1];
        for (int i = 1; i <= n; i++) {
            arr[i] = new Node(i);
        }
        for (int i = 0; i < n - 1; i++) {
            int a = in.nextInt();
            int b = in.nextInt();
            arr[a].children.add(arr[b]);
            arr[b].children.add(arr[a]);
        }
        arr[1].construct(null);
        return arr;
    }

    static class Tester {
        public static void main(String[] args) throws IOException {
            C.Validator validator = new C.Validator();

            File currentDir = new File(".");
            long before;
            long after;
            for (File inputFile : Arrays.stream(currentDir.listFiles())
                    .sorted(Comparator.comparing(File::getName))
                    .collect(Collectors.toList())) {
                if (!inputFile.getName().startsWith("input")
                        || inputFile.getName().contains("sight")
                        || inputFile.getName().contains("big")) continue;
                System.out.println("Test file: " + inputFile.getName());

                before = System.nanoTime();
                String outputFileName = "output" + inputFile.getName().substring(5);
                C.main(new String[]{inputFile.getName(), outputFileName});
                after = System.nanoTime();

                File outputFile = new File(outputFileName);
                if (!outputFile.exists()) {
                    throw new IllegalStateException("Missing output file " + outputFile);
                }

                // TODO if verifier is implemented, remove this
                if (CONSTRUCTIVE) {
                    System.out.println("INPUT:");
                    printFile(inputFile);
                    System.out.printf("\nOUTPUT: (%d milliseconds)\n", (after - before) / 1000000L);
                    printFile(outputFile);
                    continue;
                }

                if (validator.validate(inputFile, outputFile)) {
                    System.out.printf("OK (%d milliseconds)\n", (after - before) / 1000000L);
                } else {
                    System.out.println("FAILED");
                    System.out.println("\nInput: ");
                    printFile(inputFile);
                    System.out.println("\nIncorrect Output: ");
                    printFile(outputFile);
                    return;
                }
            }
            System.out.println("\n-----------------\n");

            File sightTestInput = new File("input-sight");
            if (sightTestInput.exists()) {
                System.out.println("Running sight test... Input:");
                printFile(sightTestInput);
                before = System.nanoTime();
                System.out.println("\nOutput: ");
                C.main(new String[]{"input-sight"});
                after = System.nanoTime();
                System.out.printf("(%d milliseconds)\n", (after - before) / 1000000L);
                System.out.println("\n-----------------\n");
            }

            File bigTestInput = new File("input-big");
            if (bigTestInput.exists()) {
                System.out.println("Running big test...");
                before = System.nanoTime();
                C.main(new String[] {"input-big"});
                after = System.nanoTime();
                System.out.printf("(%d milliseconds)\n", (after - before) / 1000000L);
            }
        }

        static void printFile(File file) throws FileNotFoundException {
            BufferedReader reader = new BufferedReader(new FileReader(file));
            reader.lines().forEach(System.out::println);
        }
    }

    static class Validator {
        boolean validate(File inputFile, File outputFile) throws IOException {
            File expectedOutputFile = new File("expected-output" + inputFile.getName().substring(5));
            if (CONSTRUCTIVE || !expectedOutputFile.exists()) {
                return validateManual(inputFile, outputFile);
            }
            return areSame(outputFile, expectedOutputFile);
        }

        private boolean validateManual(File inputFile, File outputFile) throws IOException {
            if (CONSTRUCTIVE) {
                // Validate output against input
                C.Reader inputReader = new C.Reader(inputFile.getName());
                C.Reader outputReader = new C.Reader(outputFile.getName());

                // TODO implement manual validation

                throw new IllegalStateException("Missing expected output file");
            } else {
                File naiveOutput = new File("naive-" + outputFile.getName());
                C.Naive.main(new String[]{inputFile.getName(), naiveOutput.getName()});

                return areSame(outputFile, naiveOutput);
            }
        }

        private boolean areSame(File file1, File file2) throws IOException {
            BufferedReader reader1 = new BufferedReader(new FileReader(file1));
            BufferedReader reader2 = new BufferedReader(new FileReader(file2));

            String line1;
            while ((line1 = reader1.readLine()) != null) {
                String line2 = reader2.readLine();
                if (line2 == null) line2 = ""; // ok if one has an extra newline
                if (!line1.trim().equals(line2.trim())) {
                    return false;
                }
            }
            String line2;
            while ((line2 = reader2.readLine()) != null) {
                if (!line2.trim().isEmpty()) {
                    return false;
                }
            }
            return true;
        }

    }

    static class Naive {
        public static void solveNaive(C.Reader in, PrintWriter out) {
            throw new IllegalStateException("missing expected output file");
        }

        public static void main(String[] args) throws IOException {
            C.Reader in = null;
            PrintWriter out = null;
            for (String arg : args) {
                if (arg.startsWith("input")) {
                    in = new C.Reader(arg);
                } else if (arg.startsWith("output")) {
                    out = new PrintWriter(new FileWriter(arg));
                }
            }
            if (in == null) in = new C.Reader();
            if (out == null) out = new PrintWriter(new OutputStreamWriter(System.out));

            int tests = in.nextInt();
            for (int t = 0; t < tests; t++) {
                solve(in, out);
            }

            out.flush();
            out.close();
        }
    }

    static long pair(int x, int y) {
        return x * BIG + y;
    }

    static int x(long pair) {
        return (int) (pair / BIG);
    }

    static int y(long pair) {
        return (int) (pair % BIG);
    }

    static class Reader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public Reader() {
            reader = new BufferedReader(new InputStreamReader(System.in), 32768);
            tokenizer = null;
        }

        public Reader(String fileName) throws FileNotFoundException {
            reader = new BufferedReader(new FileReader(fileName));
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public int[] nextInts(int n) {
            int[] out = new int[n];
            for (int i = 0; i < n; i++) {
                out[i] = nextInt();
            }
            return out;
        }

        public long[] nextLongs(int n) {
            long[] out = new long[n];
            for (int i = 0; i < n; i++) {
                out[i] = nextLong();
            }
            return out;
        }
    }
}