Problem Description

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.

Input Format

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 Format

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

6 2
1 2
2 3
4 3
2 5
6 5
3 6
4 5

4

Hint

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<n \leq 10^3$ is guaranteed.

For $100\%$ of the testdata, $1<n \leq 10^{5}$ and $1 \leq m \leq \frac{n}{2}$ are guaranteed.

Lanqiao Cup 2023 Provincial Contest B Group, Problem J.

Translated by ChatGPT 5