#P9246. [蓝桥杯 2023 省 B] 砍树

    ID: 10417 远端评测题 1000ms 512MiB 尝试: 0 已通过: 0 难度: 4 上传者: 标签>2023最近公共祖先 LCA蓝桥杯省赛

[蓝桥杯 2023 省 B] 砍树

题目描述

给定一棵由 nn 个结点组成的树以及 mm 个不重复的无序数对 $\left(a_{1},b_{1}\right),\left(a_{2},b_{2}\right),\ldots,\left(a_{m},b_{m}\right)$,其中 aia_{i} 互不相同,bib_{i} 互不相同,aibj(1i,jm)a_{i} \neq b_{j}(1 \leq i,j \leq m)

小明想知道是否能够选择一条树上的边砍断,使得对于每个 (ai,bi)\left(a_{i},b_{i}\right) 满足 aia_{i}bib_{i} 不连通,如果可以则输出应该断掉的边的编号 (编号按输入顺序从 11 开始),否则输出 -1

输入格式

输入共 n+mn+m 行,第一行为两个正整数 n,mn,m

后面 n1n-1 行,每行两个正整数 xi,yix_{i},y_{i} 表示第 ii 条边的两个端点。

后面 mm 行,每行两个正整数 ai,bia_{i},b_{i}

输出格式

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

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

4

提示

【样例说明】

断开第 22 条边后形成两个连通块:{3,4},{1,2,5,6}\{3,4\},\{1,2,5,6\},满足 3366 不连通,4455 不连通。

断开第 44 条边后形成两个连通块:{1,2,3,4},{5,6}\{1,2,3,4\},\{5,6\},同样满足 3366 不连通,4455 不连通。

44 编号更大,因此答案为 44

【评测用例规模与约定】

对于 30%30 \% 的数据,保证 1<n1031<n \leq 10^3

对于 100%100 \% 的数据,保证 1<n1051<n \leq 10^{5}1mn21 \leq m \leq \frac{n}{2}

蓝桥杯 2023 省赛 B 组 J 题。