OvelappingPath.java

import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.InputMismatchException;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.io.OutputStream;
import java.io.Writer;
import java.util.LinkedList;

class OverlappingPathSolution {
    static InputReader in = new InputReader(System.in);
    static OutputWriter out = new OutputWriter(System.out);
    static ArrayList<Integer> path;
    static class Graph {
        int V;
        LinkedList<Integer>[] adjListArray;
        Graph(int V) {
            this.V = V;
            adjListArray = new LinkedList[V];
            for(int i = 0; i < V ; i++){
                adjListArray[i] = new LinkedList<Integer>();
            }
        }
    }

    static void addEdge(Graph graph, int src, int dest) {
        graph.adjListArray[src].add(dest);
        graph.adjListArray[dest].add(src);
    }

    static void depthFirstSearch(Graph graph, int source, int dest, boolean[] visited) {
        visited[source] = true;
        path.add(source);
        if(source == dest) return;
        for(int i = 0; i < graph.adjListArray[source].size(); ++i) {
            if(!visited[graph.adjListArray[source].get(i)]) {
                depthFirstSearch(graph, graph.adjListArray[source].get(i), dest, visited);
            }
        }
    }

    static void depthFirstSearch(Graph graph, int source, int dest) {
        boolean[] visited = new boolean[graph.V];
        path = new ArrayList<>();
        depthFirstSearch(graph, source, dest, visited);
    }
    static void printGraph(Graph graph) {
        for(int v = 1; v < graph.V; v++) {
            out.printLine("Adjacency list of vertex "+ (v));
            out.print("head : ");
            for(Integer pCrawl: graph.adjListArray[v]){
                out.print(" -> "+(pCrawl));
            }
            out.printLine("\n");
        }
    }

    public static int findMaxGCD() {
        // Computing highest element
        int n = path.size();
        int high = 0;
        for (int i = 0; i < n; i++)
            high = Math.max(high, path.get(i));

        // Array to store the count of divisors
        // i.e. Potential GCDs
        int divisors[] =new int[high + 1];

        // Iterating over every element
        for (int i = 0; i < n; i++)
        {
            // Calculating all the divisors
            for (int j = 1; j <= Math.sqrt(path.get(i)); j++)
            {
                // Divisor found
                if (path.get(i) % j == 0)
                {
                    // Incrementing count for divisor
                    divisors[j]++;

                    // Element/divisor is also a divisor
                    // Checking if both divisors are
                    // not same
                    if (j != path.get(i) / j)
                        divisors[path.get(i) / j]++;
                }
            }
        }

        // Checking the highest potential GCD
        for (int i = high; i >= 1; i--)

            // If this divisor can divide at least 2
            // numbers, it is a GCD of at least 1 pair
            if (divisors[i] > 1)
                return i;
        return 1;
    }
    public static void main(String[] args) throws IOException {

        int t = in.readInt();
        while (t-- > 0) {
            int nodes = in.readInt();
            Graph graph = new Graph(nodes + 1);
            for (int i = 0; i < nodes - 1; ++i) {
                addEdge(graph, in.readInt(), in.readInt());
            }
            int u = in.readInt();
            int v = in.readInt();
            depthFirstSearch(graph, u, v);
            out.printLine(path);
            out.printLine(findMaxGCD());
        }
        out.flush();
        out.close();

    }

    private static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private SpaceCharFilter filter;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {
            if (numChars == -1) {
                throw new InputMismatchException();
            }
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0) {
                    return -1;
                }
            }
            return buf[curChar++];
        }

        public int readInt() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9') {
                    throw new InputMismatchException();
                }
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public String readString() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isSpaceChar(c));
            return res.toString();
        }

        public double readDouble() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            double res = 0;
            while (!isSpaceChar(c) && c != '.') {
                if (c == 'e' || c == 'E') {
                    return res * Math.pow(10, readInt());
                }
                if (c < '0' || c > '9') {
                    throw new InputMismatchException();
                }
                res *= 10;
                res += c - '0';
                c = read();
            }
            if (c == '.') {
                c = read();
                double m = 1;
                while (!isSpaceChar(c)) {
                    if (c == 'e' || c == 'E') {
                        return res * Math.pow(10, readInt());
                    }
                    if (c < '0' || c > '9') {
                        throw new InputMismatchException();
                    }
                    m /= 10;
                    res += (c - '0') * m;
                    c = read();
                }
            }
            return res * sgn;
        }

        public long readLong() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            long res = 0;
            do {
                if (c < '0' || c > '9') {
                    throw new InputMismatchException();
                }
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public boolean isSpaceChar(int c) {
            if (filter != null) {
                return filter.isSpaceChar(c);
            }
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public String next() {
            return readString();
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);
        }
    }

    private static class OutputWriter {
        private final PrintWriter writer;

        public OutputWriter(OutputStream outputStream) {
            writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
        }

        public OutputWriter(Writer writer) {
            this.writer = new PrintWriter(writer);
        }

        public void print(Object... objects) {
            for (int i = 0; i < objects.length; i++) {
                if (i != 0) {
                    writer.print(' ');
                }
                writer.print(objects[i]);
            }
            writer.flush();
        }

        public void printLine(Object... objects) {
            print(objects);
            writer.println();
            writer.flush();
        }

        public void close() {
            writer.close();
        }

        public void flush() {
            writer.flush();
        }
    }

    private static class IOUtils {

        public static int[] readIntArray(InputReader in, int size) {
            int[] array = new int[size];
            for (int i = 0; i < size; i++)
                array[i] = in.readInt();
            return array;
        }

    }
}