Toggle navigation
C语言网
教程
博客
团队
训练
训练
题库
题集
状态
排名
比赛
比赛
标准
自主
考试
网课
AI助手
AI助手
代码解释
语言转换
编程助手
代码查错
SQL转换
代码生成
3157 问题 H: 蓝桥杯2023年第十四届省赛真题-砍树
时间限制: 1s
内存限制: 256MB
提交: 2969 解决: 647
题目描述
给定一棵由 n 个结点组成的树以及 m 个不重复的无序数对 (a
1
, b
1
), (a
2
, b
2
),
. . . , (a
m
, b
m
),其中 a
i
互不相同,b
i
互不相同,a
i
≠ b
j
(1 ≤ i, j ≤ m)。
小明想知道是否能够选择一条树上的边砍断,使得对于每个 (a
i
, b
i
) 满足 a
i
和 b
i
不连通,如果可以则输出应该断掉的边的编号(编号按输入顺序从 1 开始),否则输出 -1.
输入
输入共 n + m 行,第一行为两个正整数 n,m。
后面 n − 1 行,每行两个正整数 x
i
,y
i
表示第 i 条边的两个端点。
后面 m 行,每行两个正整数 a
i
,b
i
。
输出
一行一个整数,表示答案,如有多个答案,输出编号最大的一个。
样例输入
6 2 1 2 2 3 4 3 2 5 6 5 3 6 4 5 4
样例输出
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。
对于 30% 的数据,保证 1 < n ≤ 1000。
对于 100% 的数据,保证 1 < n ≤ 10
5
,1 ≤ m ≤ 2/n。
C
C++
Java
Python
PHP
代码重置
开启O2优化
提交
比赛公告
2023年蓝桥杯比赛大学B组省赛题目以及团队成员皆可参加员无需密码,其他人需要密码进入比赛。
比赛状况
比赛介绍
题目列表
提交状态
比赛排名
OI赛制排名
综合统计