class _3A
{
    /* Helper function that allocates a new node with the
    given data and null left and right pointers. */
    static Node getNode(int data)
    {
        Node newNode = new Node();
        newNode.data = data;
        newNode.children = new ArrayList<>();
        return newNode;
    }

    // Function to check if there is a path from root
    // to the given node. It also populates
    // 'arr' with the given path
    static boolean getPath(Node root, List<Node> arr, int x)
    {
        // if root is null
        // there is no path
        if (root==null)
            return false;

        // push the node's value in 'arr'
        arr.add(root);

        // if it is the required node
        // return true
        if (root.data == x)
            return true;

        // else check whether the required node lies
        // in the left subtree or right subtree of
        // the current node
        boolean checkFlag = false;
        for (Node child : root.children)
            checkFlag = checkFlag || getPath(child, arr, x);
        if (checkFlag) return true;

        // required node does not lie either in the
        // left or right subtree of the current node
        // Thus, remove current node's value from
        // 'arr'and then return false
        arr.remove(arr.size()-1);
        return false;
    }

    // any two nodes in a tree
    static List<Node> pathBetweenNodes(Node root, int n1, int n2)
    {
        // List to store the path of
        // first node n1 from root
        List<Node> path1= new ArrayList<>();

        // List to store the path of
        // second node n2 from root
        List<Node> path2=new ArrayList<>();

        getPath(root, path1, n1);
        getPath(root, path2, n2);

        int intersection = -1;

        // Get intersection point
        int i = 0, j = 0;
        while (i != path1.size() || j != path2.size()) {
            // Keep moving forward until no intersection
            // is found
            if (i == j && path1.get(i) == path2.get(i)) {
                i++;
                j++;
            }
            else {
                intersection = j - 1;
                break;
            }
        }

        List<Node> path = new ArrayList<>();
        // get general path between nodes
        for (i = path1.size() - 1; i > intersection; i--)
            path.add(path1.get(i));

        for (i = intersection; i < path2.size(); i++)
            path.add(path2.get(i));
        return path;
    }
}