×

计蒜客

  1. 题库
  2. 又是一道简单题
  3. 问答
  • 18.12%
  • 65536K

题目描述

给出一棵有根树,每次查询给出两个节点 u 和 v,假设节点 f 是u,v的最近公共祖先,请查询以 f 为根的子树中,不在 u 到 v 这条链上且标号最小的节点。

输入格式

第一行输入正整数 T(T <= 30),表示共有T组输入数据。

对于每组数据,第一行输入两个正整数 n,m(n <= 50000,m <= 50000),表示节点数和询问数,节点编号 1 到 n,其中 1 是根节点。

接下来 n - 1 行,每行输入两个正整数u,v,表示标号为u和v的节点间有一条边。

接下来 m 行,每行输入两个正整数u,v,表示一次询问。

保证所有输入数据均合法。

输出格式

对于每次询问,输出答案。如不存在输出-1。

样例输入

1
3 3
1 2
1 3
1 2
1 3
2 3

样例输出

3
2
-1

题目来源

北方大学 ACM 多校训练赛 第十四场

想挑战这道题吗

  • main.c