77. 砍树
内存限制：256 MB
时间限制：1.000 S
题目描述
给定一颗由 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。
输出
一行一个整数，表示答案，如有多个答案，输出编号最大的一个。
样例输入 复制
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。