[蓝桥杯 2023 省 B] 砍树

Luogu
IDLGP9246
Time1000ms
Memory512MB
DifficultyP4
2023最近公共祖先 LCA蓝桥杯省赛
给定一棵由 $n$ 个结点组成的树以及 $m$ 个不重复的无序数对 $\left(a_{1},b_{1}\right),\left(a_{2},b_{2}\right),\ldots,\left(a_{m},b_{m}\right)$,其中 $a_{i}$ 互不相同,$b_{i}$ 互不相同,$a_{i} \neq b_{j}(1 \leq i,j \leq m)$。 小明想知道是否能够选择一条树上的边砍断,使得对于每个 $\left(a_{i},b_{i}\right)$ 满足 $a_{i}$ 和 $b_{i}$ 不连通,如果可以则输出应该断掉的边的编号 (编号按输入顺序从 $1$ 开始),否则输出 `-1`。 ## Input 输入共 $n+m$ 行,第一行为两个正整数 $n,m$。 后面 $n-1$ 行,每行两个正整数 $x_{i},y_{i}$ 表示第 $i$ 条边的两个端点。 后面 $m$ 行,每行两个正整数 $a_{i},b_{i}$。 ## Output 一行一个整数,表示答案,如有多个答案,输出编号最大的一个。 [samples] ## Note **【样例说明】** 断开第 $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 \leq 10^3$。 对于 $100 \%$ 的数据,保证 $1<n \leq 10^{5}$,$1 \leq m \leq \frac{n}{2}$。 蓝桥杯 2023 省赛 B 组 J 题。
Samples
Input #1
6 2
1 2
2 3
4 3
2 5
6 5
3 6
4 5
Output #1
4
API Response (JSON)
{
  "problem": {
    "name": "[蓝桥杯 2023 省 B] 砍树",
    "description": {
      "content": "给定一棵由 $n$ 个结点组成的树以及 $m$ 个不重复的无序数对 $\\left(a_{1},b_{1}\\right),\\left(a_{2},b_{2}\\right),\\ldots,\\left(a_{m},b_{m}\\right)$,其中 $a_{i}$ 互不相同,$b_{i}$ 互不相同,$a_{i} \\neq b_{j}(1 \\leq i,j \\leq m)$。 小明想知道是否能够选择一条",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9246"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给定一棵由 $n$ 个结点组成的树以及 $m$ 个不重复的无序数对 $\\left(a_{1},b_{1}\\right),\\left(a_{2},b_{2}\\right),\\ldots,\\left(a_{m},b_{m}\\right)$,其中 $a_{i}$ 互不相同,$b_{i}$ 互不相同,$a_{i} \\neq b_{j}(1 \\leq i,j \\leq m)$。\n\n小明想知道是否能够选择一条...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments