专业做化妆品的网站有哪些,个人网站 备案,网站开发中间商怎么做,建设网站公开教学视频下载给定一棵由 n 个结点组成的树以及 m 个不重复的无序数对 (a1, b1), (a2, b2), . . . , (am, bm)#xff0c;其中 ai 互不相同#xff0c;bi 互不相同#xff0c;ai ≠ bj(1 ≤ i, j ≤ m)。 小明想知道是否能够选择一条树上的边砍断#xff0c;使得对于每个 (ai , bi) 满足…给定一棵由 n 个结点组成的树以及 m 个不重复的无序数对 (a1, b1), (a2, b2), . . . , (am, bm)其中 ai 互不相同bi 互不相同ai ≠ bj(1 ≤ i, j ≤ m)。 小明想知道是否能够选择一条树上的边砍断使得对于每个 (ai , bi) 满足 ai和 bi 不连通如果可以则输出应该断掉的边的编号编号按输入顺序从 1 开始否则输出 -1.
输入格式 输入共 n m 行第一行为两个正整数 nm。 后面 n − 1 行每行两个正整数 xiyi 表示第 i 条边的两个端点。 后面 m 行每行两个正整数 aibi。
#include iostream
#includebits/stdc.h
#define int long long using namespace std;
typedef pairint ,intpii;
const int N1e510;vectorintedge[N];//存储图存邻接表int m,n;
int w[N];//每一个边的边权mappii,intid;//存储边的编号bool dfs(int s,int u,int father,int v )
{if(uv){return true;}for(int i0;iedge[u].size();i){int sonedge[u][i];if(sonfather)continue;if(dfs(s,son,u,v)){int IDid[{u,son}];w[ID];return true;}}return false;}
void solve()
{cinnm;for(int i0;in-1;i){int x,y;cinxy;edge[x].push_back(y);edge[y].push_back(x);id[{x,y}]id[{y,x}]i;}for(int i0;im;i){int x,y;cinxy;dfs(x,x,-1,y);}int ans-1;for(int in-1;i0;i--){if(w[i]m){ansi1;//题目是从1开始编号break;}}coutansendl;}
signed main()
{// 请在此输入您的代码ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t1;//cintwhile(t--)solve();return 0;
}
