#P9246. [蓝桥杯 2023 省 B] 砍树
[蓝桥杯 2023 省 B] 砍树
题目描述
给定一棵由 个结点组成的树以及 个不重复的无序数对 $\left(a_{1},b_{1}\right),\left(a_{2},b_{2}\right),\ldots,\left(a_{m},b_{m}\right)$,其中 互不相同, 互不相同,。
小明想知道是否能够选择一条树上的边砍断,使得对于每个 满足 和 不连通,如果可以则输出应该断掉的边的编号 (编号按输入顺序从 开始),否则输出 -1
。
输入格式
输入共 行,第一行为两个正整数 。
后面 行,每行两个正整数 表示第 条边的两个端点。
后面 行,每行两个正整数 。
输出格式
一行一个整数,表示答案,如有多个答案,输出编号最大的一个。
6 2
1 2
2 3
4 3
2 5
6 5
3 6
4 5
4
提示
【样例说明】
断开第 条边后形成两个连通块:,满足 和 不连通, 和 不连通。
断开第 条边后形成两个连通块:,同样满足 和 不连通, 和 不连通。
编号更大,因此答案为 。
【评测用例规模与约定】
对于 的数据,保证 。
对于 的数据,保证 ,。
蓝桥杯 2023 省赛 B 组 J 题。