给定一棵由 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。
#include <iostream>
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int ,int>pii;
const int N=1e5+10;
vector<int>edge[N];//存储图（存邻接表）
int m,n;
int w[N];//每一个边的边权
map<pii,int>id;//存储边的编号
bool dfs(int s,int u,int father,int v )
{
if(u==v){
return true;
}
for(int i=0;i<edge[u].size();i++)
{
int son=edge[u][i];
if(son==father)
continue;
if(dfs(s,son,u,v))
{
int ID=id[{u,son}];
w[ID]++;
return true;
}
}
return false;
}
void solve()
{
cin>>n>>m;
for(int i=0;i<n-1;i++)
{
int x,y;
cin>>x>>y;
edge[x].push_back(y);
edge[y].push_back(x);
id[{x,y}]=id[{y,x}]=i;
}
for(int i=0;i<m;i++)
{
int x,y;
cin>>x>>y;
dfs(x,x,-1,y);
}
int ans=-1;
for(int i=n-1;i>=0;i--)
{
if(w[i]==m)
{
ans=i+1;//题目是从1开始编号
break;
}
}
cout<<ans<<endl;
}
signed main()
{
// 请在此输入您的代码
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t=1;
//cin>>t
while(t--)
solve();
return 0;
}