Tree
Given: an ordered rooted tree T and a list of its modifications. The modifications are the following: cut off node with the given number along with the subtree from its current parent node and add it as a rightmost child node to the other node.
You must determine the modification after which the tree becomes isomorphic to one of the previous trees.
In a rooted ordered tree each non-leaf node has an established order of child nodes. Two trees are considered isomorphic if the following is retained in bijective mapping:
the parent-child relation, as in "the node s is a child of the node f",
the order of children for every node.
Input
The first line of the input file contains two integers: N is the number of nodes in the tree and M is the number of modifications (2 ≤ N ≤ 100000, 1 ≤ M ≤ 100000). The tree nodes are numbered by integer numbers from 1 to N. The root node has the number 1.
The following N lines contain ordered lists of child nodes for the nodes of the initial tree. Each i-th list is described by the number K_i of children of the i-th node and by the sequence of its child node numbers (0≤ K_i ≤ N–1).
The remaining M lines contain the description of the tree modifications. Each modification is defined by two integers S_j and F_j – – the number of the node being cut from the parent along with its subtree and the number of the node to which it is added as its rightmost child (2 ≤ S_j ≤ N, 1 ≤ F_j ≤ N). It is guaranteed that the node F_j is not a descendant of the node S_j and does not coincide with it.
Output
If all M+1 resulting trees are different, the output file must contain the number –1. Otherwise it must contain two integers A and B separated by a space — the numbers of two isomorphic trees (0 ≤ A < B ≤ M). If there are several pairs of isomorphic trees, the output file must contain the pair with the lowest number B.
Trees are numbered in the following way: the initial tree has the number 0, and j-th modification results in j-th tree (1 ≤ j ≤ M).
Comment
Below are some of the trees for the first test from the given data.
