题目描述

AcWing 4963 给定一棵由 n 个结点组成的树以及 m 个不重复的无序数对 (a1,b1),(a2,b2),...,(am,bm)，其中 ai 互不相同，bi 互不相同，ai≠bj(1≤i,j≤m)。 小明想知道是否能够选择一条树上的边砍断，使得对于每个 (ai,bi) 满足 ai 和 bi 不连通，如果可以则输出应该断掉的边的编号（编号按输入顺序从 1 开始），否则输出 -1。

输入格式

输入共 n+m 行，第一行为两个正整数 n,m。 后面 n-1 行，每行两个正整数 xi,yi 表示第 i 条边的两个端点。 后面 m 行，每行两个正整数 ai,bi。

输出格式

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

样例

输入样例 1

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

输出样例 1

4

输入样例 2

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

输出样例 2

4

输入样例 3

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

输出样例 3

-1

提示

数据范围：1<n≤105，1≤m≤n/2。

样例解释：断开第 2 条边后形成两个连通块：{3,4}，{1,2,5,6}，满足 3 和 6 不连通，4 和 5 不连通。 断开第 4 条边后形成两个连通块：{1,2,3,4}，{5,6}，同样满足 3 和 6 不连通，4 和 5 不连通。 4 编号更大，因此答案为 4。

思路：分析样例，可知，只要被删除的是 m 个路径的公共边，就可以达成目标。 即只要统计边被经过的次数，次数==m 的边就是公共边，其中编号最大的就是答案。 这个问题就变成树上边差分问题。