На собеседовании в одну крупную авиакомпанию в качестве испытания кандидату предлагают сыграть в особые шахматы. Здесь шахматное поле представлено в виде неориентированного графа, состоящего из $$$n$$$ вершин, соединенных $$$m$$$ ребрами двух цветов — белого и черного. В вершинах с номерами $$$k$$$ и $$$q$$$ расположены фигуры короля и ферзя соответственно. Кандидат может выбрать, за какую фигуру он будет играть, а собеседующий выберет оставшуюся. Игроки выполняют ходы поочередно, первым ходит игрок, играющий за фигуру $$$X$$$. За один ход король может перемещаться в любую вершину, соединенную ребром с текущей, а ферзь может перемещаться в любую вершину, до которой существует путь из текущей вершины, состоящий из ребер одного цвета. Побеждает игрок, после хода которого фигуры оказались в одной вершине. Если побеждает кандидат, то собеседование считается пройденным.
Теперь вы интересуетесь для некоторых конфигураций игры $$$k$$$, $$$q$$$ и $$$X$$$, за какую фигуру нужно играть, чтобы гарантировать победу и, естественно, успешное прохождение собеседования.
Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 50$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
В первой строке набора входных данных задано три целых числа $$$n$$$, $$$m$$$ и $$$l$$$ ($$$2 \le n \le 100$$$, $$$1 \le m \le 100$$$, $$$1 \le l \le 5 \cdot 10^5$$$) — количество вершин в графе, ребер и количество конфигураций игры соответственно.
В следующих $$$m$$$ строках задано по 3 целых числа $$$u$$$, $$$v$$$ и $$$c$$$ ($$$1 \le u, v \le n$$$, $$$u \ne v$$$, $$$c \in \{1, 2\}$$$) — номера вершин, соединенных ребром, и цвет ребра. Гарантируется, что граф состоит из одной компоненты связности и не содержит кратных ребер.
В следующих $$$l$$$ строках задано два целых числа $$$k$$$ и $$$q$$$ ($$$1 \le k, q \le n$$$, $$$k \ne q$$$) и строка $$$X$$$ — номера вершин, где расположены король и ферзь, и название фигуры, которая должна выполнить первый ход. Если задано «queen» (без кавычек), то первым ходит игрок, играющий за ферзя, если «king» (без кавычек) — игрок, играющий за короля.
Гарантируется, что сумма $$$n$$$ и сумма $$$m$$$ по всем наборам входных данных не превышают $$$100$$$, а сумма $$$l$$$ не превышает $$$5 \cdot 10^5$$$.
Для каждого набора входных данных для каждой конфигурации игры выведите «king» (без кавычек), если кандидат должен выбрать короля, чтобы гарантировать победу, «queen» (без кавычек), если кандидат должен выбрать ферзя, и «draw» (без кавычек), если кандидат не сможет гарантировать победу, играя за одну из фигур.
24 4 21 2 12 3 23 4 14 1 21 3 king1 3 queen6 6 11 2 12 3 23 4 14 5 25 6 16 1 21 3 queen
queen king draw
| BSUIR Open XIII: Школьный финал |
|---|
| Закончено |
