H. Слизни и запросы
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Вам дано дерево из $$$n$$$ вершин, пронумерованных от $$$1$$$ до $$$n$$$. Слизень занимает ровно $$$m$$$ вершин дерева. Гарантируется, что подграф, порождённый занятыми вершинами, является связным.

Изначально слизень занимает вершины $$$s_1,s_2,\ldots,s_m$$$.

Сначала определим функцию $$$f$$$ на последовательности вершин. Рассмотрим последовательность $$$a_1,a_2,\ldots,a_k$$$. Имеется $$$k$$$ кусочков еды. Для каждого $$$i$$$ $$$i$$$-й кусочек еды находится в вершине $$$a_i$$$. Изначально на дереве находится только первый кусочек еды.

Слизень может выполнять следующие операции любое количество раз:

  • Передвижение. Слизень покидает одну из текущих занятых вершин и расширяется на одну из текущих незанятых вершин.

    Формально, пусть $$$S$$$ — текущее множество занятых вершин. Выбрать вершину $$$u\in S$$$ и вершину $$$v\notin S$$$ и заменить $$$S$$$ на $$$(S\setminus{u})\cup{v}$$$. После операции подграф, порождённый $$$S$$$, должен оставаться связным.

  • Поедание. Если $$$i$$$-й кусочек еды уже появился и слизень в данный момент занимает вершину $$$a_i$$$, то слизень может съесть $$$i$$$-й кусочек еды. Если $$$1\le i \lt k$$$, то $$$(i+1)$$$-й кусочек еды появляется сразу после этого. Поедание не изменяет занятые вершины.

Определим $$$f([a_1,a_2,\ldots,a_k])$$$ как минимальное количество операций Передвижение, необходимых слизню для того, чтобы съесть все $$$k$$$ кусочков еды по порядку, начиная с изначально занятых вершин $$$s_1,s_2,\ldots,s_m$$$.

Имеется $$$q$$$ запросов. Вам нужно отвечать на запросы в режиме онлайн: На вход подаются закодированные значения $$$p_1,p_2,\ldots,p_q$$$. Пусть $$$\mathrm{ans}_0=0$$$. Для каждого $$$i=1,2,\ldots,q$$$ фактическая вершина $$$i$$$-го запроса равна $$$c_i=((p_i-1+\mathrm{ans}_{i-1}) \bmod n)+1$$$, где $$$\mathrm{ans}_i=f([c_1,c_2,\ldots,c_i])$$$.

Для каждого $$$i=1,2,\ldots,q$$$ выведите $$$\mathrm{ans}_i$$$.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит три целых числа $$$n$$$, $$$m$$$ и $$$q$$$ ($$$2\le m\le n\le 10^5$$$, $$$1\le q\le 10^5$$$) — количество вершин в дереве, количество вершин, занятых слизнем, и количество запросов.

Каждая из следующих $$$n-1$$$ строк содержит два целых числа $$$u$$$ и $$$v$$$ ($$$1\le u,v\le n$$$, $$$u\ne v$$$), обозначающих ребро дерева.

Следующая строка содержит $$$m$$$ различных целых чисел $$$s_1,s_2,\ldots,s_m$$$ ($$$1\le s_i\le n$$$) — вершины, изначально занятые слизнем. Гарантируется, что эти вершины порождают связный подграф.

Следующая строка содержит $$$q$$$ целых чисел $$$p_1,p_2,\ldots,p_q$$$ ($$$1\le p_i\le n$$$) — закодированные вершины запросов.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$.

Гарантируется, что сумма значений $$$q$$$ по всем наборам входных данных не превосходит $$$10^5$$$.

Выходные данные

Для каждого набора входных данных выведите $$$q$$$ целых чисел. $$$i$$$-е целое число должно быть равно $$$\mathrm{ans}_i$$$.

Пример
Входные данные
10
5 2 3
3 5
2 1
4 3
3 2
1 2
1 4 3
6 3 4
5 1
1 3
6 1
4 1
2 1
1 2 3
5 2 5 6
7 3 5
3 7
4 2
1 3
2 1
6 3
5 2
1 2 4
7 3 2 5 2
5 2 5
3 1
1 5
2 1
4 1
1 2
3 3 3 4 2
6 3 6
4 6
3 2
1 2
5 4
2 4
2 4 5
6 6 1 2 4 6
7 4 5
5 2
3 1
2 1
3 7
6 3
4 2
1 2 3 4
7 4 4 5 1
4 3 4
3 1
1 4
2 1
1 2 3
4 1 2 3
6 2 5
2 4
5 4
2 1
6 4
3 2
1 2
6 1 1 1 2
7 2 5
2 4
7 3
3 6
1 3
1 2
5 2
1 2
4 6 1 6 5
8 4 6
5 2
3 2
7 5
4 3
8 7
1 2
6 5
2 3 4 5
8 7 3 3 7 8
Выходные данные
0 2 3 
1 1 2 3 
2 4 6 8 9 
1 2 3 4 4 
1 2 3 4 4 4 
1 2 3 3 4 
1 1 2 2 
2 4 6 8 9 
1 4 7 10 11 
2 3 4 4 5 5
Примечание

В пояснениях ниже подчёркнутая вершина — это вновь занятая вершина после операции Передвижение, а вершины, в которых слизень поедает еду, выделены жирным шрифтом.

В первом наборе входных данных после декодирования еда появляется в вершинах $$$1,4,5$$$ по порядку. Изначально слизень занимает $$$[1,2]$$$.

  1. Для $$$[1]$$$ слизень уже занимает вершину $$$\mathbf{1}$$$, поэтому $$$\mathrm{ans}_1=0$$$.
  2. Для $$$[1,4]$$$ один из оптимальных процессов: $$$[\mathbf{1},2]\to[2,\underline{3}]\to[3,\underline{\mathbf{4}}]$$$, поэтому $$$\mathrm{ans}_2=2$$$.
  3. Для $$$[1,4,5]$$$ один из оптимальных процессов: $$$[\mathbf{1},2]\to[2,\underline{3}]\to[3,\underline{\mathbf{4}}]\to[3,\underline{\mathbf{5}}]$$$, поэтому $$$\mathrm{ans}_3=3$$$.

Во втором наборе входных данных после декодирования еда появляется в вершинах $$$5,3,6,2$$$ по порядку. Изначально слизень занимает $$$[1,2,3]$$$.

  1. Для $$$[5]$$$ один из оптимальных процессов: $$$[1,2,3]\to[1,3,\underline{\mathbf{5}}]$$$, поэтому $$$\mathrm{ans}_1=1$$$.
  2. Для $$$[5,3]$$$ тот же процесс также позволяет слизню поесть в вершине $$$\mathbf{3}$$$, поэтому $$$\mathrm{ans}_2=1$$$.
  3. Для $$$[5,3,6]$$$ один из оптимальных процессов: $$$[1,2,3]\to[1,3,\underline{\mathbf{5}}]\to[1,3,\underline{\mathbf{6}}]$$$, поэтому $$$\mathrm{ans}_3=2$$$.
  4. Для $$$[5,3,6,2]$$$ один из оптимальных процессов: $$$[1,2,3]\to[1,3,\underline{\mathbf{5}}]\to[1,3,\underline{\mathbf{6}}]\to[1,\underline{\mathbf{2}},3]$$$, поэтому $$$\mathrm{ans}_4=3$$$.

В третьем наборе входных данных после декодирования еда появляется в вершинах $$$7,5,6,4,3$$$ по порядку. Изначально слизень занимает $$$[1,2,4]$$$.

  1. Для $$$[7]$$$ один из оптимальных процессов: $$$[1,2,4]\to[1,2,\underline{3}]\to[1,3,\underline{\mathbf{7}}]$$$, поэтому $$$\mathrm{ans}_1=2$$$.
  2. Для $$$[7,5]$$$ один из оптимальных процессов: $$$[1,2,4]\to[1,2,\underline{3}]\to[1,3,\underline{\mathbf{7}}]\to[1,\underline{2},3]\to[1,2,\underline{\mathbf{5}}]$$$, поэтому $$$\mathrm{ans}_2=4$$$.
  3. Для $$$[7,5,6]$$$ один из оптимальных процессов: $$$[1,2,4]\to[1,2,\underline{3}]\to[1,3,\underline{\mathbf{7}}]\to[1,\underline{2},3]\to[1,2,\underline{\mathbf{5}}]\to[1,2,\underline{3}]\to[1,3,\underline{\mathbf{6}}]$$$, поэтому $$$\mathrm{ans}_3=6$$$.
  4. Для $$$[7,5,6,4]$$$ продолжаем с $$$[1,3,\mathbf{6}]\to[1,\underline{2},3]\to[1,2,\underline{\mathbf{4}}]$$$, поэтому $$$\mathrm{ans}_4=8$$$.
  5. Для $$$[7,5,6,4,3]$$$ продолжаем с $$$[1,2,\mathbf{4}]\to[1,2,\underline{\mathbf{3}}]$$$, поэтому $$$\mathrm{ans}_5=9$$$.

В четвёртом наборе входных данных после декодирования еда появляется в вершинах $$$3,4,5,2,1$$$.

В пятом наборе входных данных после декодирования еда появляется в вершинах $$$6,1,3,5,2,4$$$.

В шестом наборе входных данных после декодирования еда появляется в вершинах $$$7,5,6,1,4$$$.