题目背景

那么下面，我将对█████的头是否有独立意识进行测试。

你好，█████的头。

如果看到了这条消息，请回复。

如果看到了这条消息，请回复。

如果看到了这条消息，请回复。

如果看到了这条消息，请回复。

如果看到了这条消息，请回复。

uzjandgh aidokahquxjensgkandvxhandbgsnwbegsbsbwvhzbsbwhdhd http://███.███.███.███/problem/███bdhbeyzhXbakxokcngehdnDbekzjycwjwjd

题目描述

某天，某棵树上的你的若干个头想做一个游戏。

具体来说，你有一棵 $n$ 个节点的树，接下来你的头会在这棵树上做 $m$ 次游戏：

一次游戏里，会有你的 $k$ 个头参与，分别在 $x_1,x_2,\cdots,x_k$ 的位置，为了选手的精神健康着想，保证 $x_i$ 互不相同

你的每个头都有它最喜欢的一个头，你惊奇的发现，你的第 $i$ 个头最喜欢的头恰好是你的第 $(i\bmod k)+1$ 个头。每时每刻，所有头都会朝着它们最喜欢的头的方向以 $1$ 条边每单位时间的速度运动，注意运动是连续的。

现在，在一旁旁观的你的第 $k+1$ 个头想要知道游戏进行的怎么样，你的第 $k+1$ 个头会向你提出 $q$ 次询问，每次询问给定 $p,t$，你需要告诉它你的第 $p$ 个头在第 $t$ 时刻处在哪个位置（可能在边上，见输出格式）。

不同游戏之间 $k,q$ 可能不同，并且游戏之间相互独立。

一些移动的细节：

• 如果一个头和它最喜欢的头重合，那么你可以认为它之后都会一直跟着它喜欢的头移动。
• 如果所有头聚在一个点上，那么所有头保持不动。

输入格式

第一行两个整数 $n,m$，表示树的大小，以及游戏数。

接下来 $n-1$ 行每行两个整数 $u,v$，表示节点 $u$ 和 $v$ 之间存在一条边。

接下来依次描述 $m$ 个游戏：

第一行两个正整数 $k,q$，表示头的数量以及询问数。

第二行 $k$ 个整数 $x_1,x_2,\cdots,x_k$，表示头的初始位置。

接下来 $q$ 行每行两个整数 $p,t$，描述每个询问。

输出格式

对于每个情景，输出 $q$ 行，依次回答每个询问。

如果头的位置在点 $u$ 上，请输出 u u（用空格分隔），如果头的位置在边 $u-v$ 上，设 $u< v$，请输出 u v（用空格分隔）。

10 2
7 6
1 4
10 7
9 2
5 7
3 7
10 9
8 6
4 10
3 2
10 2 3 
1 2
1 1
4 4
9 1 8 5 
4 1
3 2
3 3
1 999999993

10 10
9 9
7 7
7 7
7 10 
7 10

提示

对于所有数据，$2\le n\le2\times10^5,2\le k\le n,1\le q\le2\times10^5,\sum k,\sum q\le4\times10^5,1\le t\le 10^9$。

subtask 1（13 pts）：$n\le3000,\sum k\le6000$，请注意并未对 $q$ 做出任何保证。

subtask 2（8 pts）：树的形态随机，随机方式为初始随机一个排列 $a_1,a_2,\cdots,a_n$，然后对于每个 $a_i(2\le i\le n)$，从 $a_1,a_2,\cdots,a_{i-1}$ 中随机选择一个连向 $a_i$。

subtask 3（14 pts）：保证树是一条链。请注意不保证这条链的编号依次为 $1\sim n$。

subtask 4（8 pts）：$k=3$。

subtask 5（8 pts）：$k=4$。

subtask 6（17 pts）：$k\le30$。

subtask 7（16 pts）：$n\le10^5,\sum k\le2\times10^5$。

subtask 8（16 pts）：无特殊限制。