题目描述

给定一棵由 $n$ 个结点组成的树以及 $m$ 个不重复的无序数对 $\left(a_{1},b_{1}\right),\left(a_{2},b_{2}\right),\ldots,\left(a_{m},b_{m}\right)$，其中 $a_{i}$ 互不相同，$b_{i}$ 互不相同，$a_{i} \neq b_{j}(1 \leq i,j \leq m)$。

小明想知道是否能够选择一条树上的边砍断，使得对于每个 $\left(a_{i},b_{i}\right)$ 满足 $a_{i}$ 和 $b_{i}$ 不连通，如果可以则输出应该断掉的边的编号 (编号按输入顺序从 $1$ 开始)，否则输出 -1。

输入格式

输入共 $n+m$ 行，第一行为两个正整数 $n,m$。

后面 $n-1$ 行，每行两个正整数 $x_{i},y_{i}$ 表示第 $i$ 条边的两个端点。

后面 $m$ 行，每行两个正整数 $a_{i},b_{i}$。

输出格式

一行一个整数，表示答案，如有多个答案，输出编号最大的一个。

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

4

提示

【样例说明】

断开第 $2$ 条边后形成两个连通块：$\{3,4\},\{1,2,5,6\}$，满足 $3$ 和 $6$ 不连通，$4$ 和 $5$ 不连通。

断开第 $4$ 条边后形成两个连通块：$\{1,2,3,4\},\{5,6\}$，同样满足 $3$ 和 $6$ 不连通，$4$ 和 $5$ 不连通。

$4$ 编号更大，因此答案为 $4$。

【评测用例规模与约定】

对于 $30 \%$ 的数据，保证 $1<n \leq 10^3$。

对于 $100 \%$ 的数据，保证 $1<n \leq 10^{5}$，$1 \leq m \leq \frac{n}{2}$。

蓝桥杯 2023 省赛 B 组 J 题。