| Codeforces Global Round 1 |
|---|
| Закончено |
Игра в крестики-нолики начинается на дереве из $$$n$$$ вершин. Некоторые вершины уже окрашены в белый цвет, а остальные пока бесцветны.
Есть два игрока — белый и чёрный. Игроки ходят по очереди, белый игрок начинает игру. В свой ход игрок выбирает ещё не покрашенную вершину и красит её в свой цвет.
Игрок выигрывает, если он покрасит какой-нибудь путь из трёх вершин в свой цвет. В случае, если все вершины становятся покрашенными, а никакой игрок так и не выиграл, то игра заканчивается вничью.
Не могли бы вы выяснить, кто выиграет эту игру или закончится ли она в ничью, если оба игрока играют оптимально?
Первая строка содержит одно целое число $$$T$$$ ($$$1 \le T \le 50\,000$$$) — количество тестовых случаев. Далее следуют описания $$$T$$$ тестовых случаев.
Первая строка каждого тестового случая содержит одно целое число $$$n$$$ ($$$1 \le n \le 5 \cdot 10^5$$$) — количество вершин в дереве.
Каждая из следующих $$$n - 1$$$ строк содержит целые числа $$$v$$$ и $$$u$$$ ($$$1 \le v, u \le n$$$), означающие, что вершины $$$u$$$ и $$$v$$$ соединены очередным ребром.
Последняя строка теста содержит строку длины $$$n$$$, состоящую из букв «W» и «N». Покрашенные в белый цвет вершины отмечены как «W».
Гарантируется, что заданные рёбра образуют дерево, что есть хотя бы одна неокрашенная вершина и что пути, состоящего из трёх белых вершин, нет.
Гарантируется, что сумма $$$n$$$ по всем тестовым случаям не превосходит $$$5 \cdot 10^5$$$.
Для каждого тестового случая выведите «White», «Draw» или «Black» в зависимости от того, кто выиграет (соответственно белый, ничья или черный).
2 4 1 2 1 3 1 4 NNNW 5 1 2 2 3 3 4 4 5 NNNNN
White Draw
В первом примере вершина $$$4$$$ уже изначально покрашена в белый. Белый игрок может выиграть покрасив своим первым ходом вершину $$$1$$$ и покрасив оставшуюся вершину своим следующим ходом. Этот процесс изображен на картинках ниже.
Во втором примере можно показать, что ни один игрок не может гарантировать себе победу.
