P9246 [Lanqiao Cup 2023 NOI Qualifier B] Cutting Trees

Given a tree with $n$ nodes and $m$ distinct unordered pairs $\left(a_{1},b_{1}\right),\left(a_{2},b_{2}\right),\ldots,\left(a_{m},b_{m}\right)$, where all $a_{i}$ are pairwise different, all $b_{i}$ are pairwise different, and $a_{i} \neq b_{j}(1 \leq i,j \leq m)$. Xiaoming wants to know whether it is possible to choose one edge in the tree and cut it, such that for every $\left(a_{i},b_{i}\right)$, $a_{i}$ and $b_{i}$ become disconnected. If it is possible, output the index of the edge that should be cut (indices start from $1$ in the input order). Otherwise, output `-1`.

The input has $n+m$ lines. The first line contains two positive integers $n,m$. The next $n-1$ lines each contain two positive integers $x_{i},y_{i}$, representing the two endpoints of the $i$-th edge. The last $m$ lines each contain two positive integers $a_{i},b_{i}$.

Output one integer in one line, representing the answer. If there are multiple answers, output the one with the largest index.

**Sample Explanation.** After cutting the $2$-nd edge, two connected components are formed: $\{3,4\},\{1,2,5,6\}$, which satisfies that $3$ and $6$ are disconnected, and $4$ and $5$ are disconnected. After cutting the $4$-th edge, two connected components are formed: $\{1,2,3,4\},\{5,6\}$, which also satisfies that $3$ and $6$ are disconnected, and $4$ and $5$ are disconnected. Since $4$ has a larger index, the answer is $4$. **Constraints.** For $30\%$ of the testdata, $1