Tree

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 \leq N \leq 100000, 1 \leq M \leq 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 \leq K_i \leq 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 \leq S_j \leq N, 1 \leq F_j \leq 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 \leq A < B \leq 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 \leq j \leq M).

Examples

Note

Below are some of the trees for the first test from the given data.