F. Blackslex и еще одна RGB-прогулка
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это задача с двойным запуском (коммуникационная).

Есть два игрока: Игрок A (Агент) и Игрок B (Blackslex ). Жюри сначала взаимодействует с игроком A. После того как игрок A завершит свое взаимодействие, жюри будет взаимодействовать с игроком B. Обратите внимание, что игрок A и игрок B не могут напрямую передавать информацию друг другу; оба игрока могут только отправлять информацию или получать информацию от жюри, но они могут согласовать стратегию, которую будут использовать для общения.

Пингвинья Республика — это двудольный связный неориентированный граф $$$G$$$ с $$$n$$$ вершинами и $$$m$$$ ребрами. Blackslex собирается провести запрещенные полевые исследования на вершине $$$1$$$. Из-за ограничений на передвижение его высадят на неизвестной вершине $$$v$$$ ($$$2 \leq v \leq n$$$). Ему нужно добраться до вершины $$$1$$$, не имея информации о графе.

Для своего путешествия он подкупил пингвиньего агента и согласовал некоторую стратегию общения, используя следующий метод: агент будет незаметно окрашивать каждую вершину в один из трех цветов: красный, зеленый или синий. С точки зрения Blackslex, он будет видеть только цвет $$$c_i$$$ каждого соседа $$$u_i$$$ ($$$1 \leq i \leq d(v)$$$$$$^{\text{∗}}$$$) вершины $$$v$$$. Он должен выбрать некоторое $$$j$$$ ($$$1 \leq j \leq d(v)$$$) и перейти к вершине $$$u_j$$$, чтобы приблизиться к вершине $$$1$$$.

Обратите внимание, что соседи упорядочены произвольным образом. Он видит только цвета соседних вершин, а не вершину, на которой находится. Кроме того, он не знает индекс вершины, на которой находится, соседние вершины или любую другую вершину.

Ваша задача — реализовать стратегию как для агента, так и для Blackslex. Для агента вы должны окрасить каждую вершину в один из трех цветов. Для Blackslex вам даны $$$q$$$ запросов. В каждом запросе вас высаживают на произвольной и неизвестной вершине $$$v$$$ и дают цвет соседних вершин. Вы должны определить вершину, к которой следует перейти, чтобы приблизиться к вершине $$$1$$$.

$$$^{\text{∗}}$$$Количество соседей вершины $$$v$$$.

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

Ваш код будет запущен ровно два раза на каждом тесте. В первый раз вы будете Игроком A (Агентом), а во второй — Игроком B (Blackslex).

Входные данные первого запуска

Первая строка входных данных содержит строку first. Это нужно для того, чтобы ваша программа распознала, что это ее первый запуск, и она должна действовать как Игрок A.

Каждый тест содержит несколько наборов входных данных. Первая строка содержит количество наборов входных данных $$$t$$$ ($$$1 \leq t \leq 10^4$$$). Описание наборов следует далее.

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

Следующие $$$m$$$ строк содержат информацию о ребрах. $$$i$$$-я ($$$1 \leq i \leq m$$$) строка содержит два целых числа $$$a_i$$$ и $$$b_i$$$. ($$$1 \leq a_i, b_i \leq n$$$, $$$a_i \neq b_i$$$) — вершина $$$a_i$$$ соединена с вершиной $$$b_i$$$ ребром $$$i$$$.

Гарантируется, что:

  • Сумма $$$n$$$ и сумма $$$m$$$ не превышают $$$10^5$$$ по всем наборам входных данных.
  • Граф в каждом наборе входных данных двудольный и связный. В нем нет дублирующихся ребер и петель.

Входные данные второго запуска

Первая строка входных данных содержит строку second. Это нужно для того, чтобы ваша программа распознала, что это ее второй запуск, и она должна действовать как Игрок B.

Каждый тест содержит несколько наборов входных данных. Первая строка содержит количество наборов входных данных $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — то же значение $$$t$$$, что и в первом запуске. Описание наборов следует далее.

Первая строка каждого набора содержит одно целое число $$$q$$$ ($$$1 \leq q \leq 10^5$$$) — количество запросов в этом наборе.

Первая строка каждого запроса содержит одно целое число $$$d(v)$$$ ($$$1 \leq d(v) \leq 10^5$$$) — количество соседей вершины $$$v$$$, на которой сейчас находится Blackslex.

Следующая строка каждого запроса содержит строку $$$c$$$ длиной $$$d(v)$$$ — $$$i$$$-й ($$$1 \leq i \leq d(v)$$$) символ строки — цвет соседней вершины $$$u_i$$$. Символы в строке — это r, g или b, представляющие красный, зеленый или синий.

Гарантируется, что:

  • Сумма $$$q$$$ не превышает $$$10^5$$$ по всем запросам во всех наборах входных данных.
  • Сумма $$$d(v)$$$ не превышает $$$2 \cdot 10^5$$$ по всем запросам во всех наборах входных данных.
  • $$$v \neq 1$$$

Входные данные второго запуска не адаптивен. Другими словами, входные данные второго запуска не изменятся в разных запусках.

Взломы

Чтобы сделать взлом, используйте следующий формат:

Первая строка содержит два целых числа $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных.

Описание наборов входных данных для первого запуска следует далее.

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

Следующие $$$m$$$ строк содержат информацию о ребрах. $$$i$$$-я ($$$1 \leq i \leq m$$$) строка содержит два целых числа $$$a_i$$$ и $$$b_i$$$. ($$$1 \leq a_i, b_i \leq n$$$, $$$a_i \neq b_i$$$) — вершина $$$a_i$$$ соединена с вершиной $$$b_i$$$ ребром $$$i$$$.

После этого следует описание наборов входных данных для второго запуска.

Первая строка каждого набора содержит одно целое число $$$q$$$ ($$$1 \leq q \leq 10^5$$$) — количество запросов в этом наборе.

Первая строка каждого запроса содержит одно целое число $$$v$$$ ($$$2 \leq v \leq n$$$) — вершина, на которой высаживается Blackslex.

Вторая строка каждого запроса содержит $$$d(v)$$$ целых чисел $$$p_1, p_2, \ldots, p_{d(v)}$$$ ($$$1 \leq p_i \leq d(v)$$$, каждое число в $$$p$$$ различно) — порядок соседей, как следует; пусть $$$q_1 \lt q_2 \lt \ldots \lt q_{d(v)}$$$ будут соседями вершины $$$v$$$, тогда порядок ввода соседей — это $$$u_i = q_{p_i}$$$.

Должно выполняться следующее:

  • Сумма $$$n$$$ и сумма $$$m$$$ не превышают $$$10^5$$$ по всем наборам входных данных в первом запуске.
  • Граф в каждом наборе двудольный и связный. В нем нет дублирующихся ребер и самопетлей.
  • Сумма $$$q$$$ не превышает $$$10^5$$$ по всем запросам во всех наборах входных данных .
  • Сумма $$$d(v)$$$ не превышает $$$2 \cdot 10^5$$$ по всем наборам входных данных во втором запуске.
Выходные данные

Для первого запуска, для каждого набора входных данных выведите одну строку $$$s$$$ длиной $$$n$$$ — $$$s_i$$$ ($$$1 \leq i \leq n$$$) — цвет $$$i$$$-й вершины, окрашенной агентом. Символы в строке — это r, g или b, представляющие красный, зеленый или синий.

Для второго запуска, для каждого запроса в каждом наборе входных данных выведите одно целое число $$$j$$$ ($$$1 \leq j \leq d(v)$$$) — $$$u_j$$$ — соседняя вершина, к которой Blackslex перейдет дальше.

Примеры
Входные данные
first
2
7 8
1 2
1 6
3 2
4 2
6 4
4 7
5 6
5 7

4 4
1 2
1 3
4 2
4 3
Выходные данные
rrgbggr
rbbb
Входные данные
second
2
2
3
grr
3
gbr

1
2
rb
Выходные данные
1
3
1
Примечание
Граф и раскраска обоих примеров.

Граф и раскраска вершин примера показаны на изображении выше.

Во втором запуске первый пример имеет два запроса.

Первый запрос на вершине $$$4$$$ с соседями, упорядоченными как вершина $$$6$$$, $$$2$$$ и $$$7$$$. Выбор первого соседа — это переход к вершине $$$6$$$.

Второй запрос на вершине $$$6$$$ с соседями, упорядоченными как вершина $$$5$$$, $$$4$$$ и $$$1$$$. Выбор третьего соседа — это переход к вершине $$$1$$$.

Во втором примере есть один запрос на вершине $$$2$$$ с соседями, упорядоченными как вершина $$$1$$$ и $$$4$$$. Выбор первого соседа — это переход к вершине $$$1$$$.

Обратите внимание, что пустые строки добавлены для удобства чтения. На самом деле наборы не имеют пустых строк.