| Codeforces Round 467 (Div. 1) |
|---|
| Закончено |
Петя и Вася договорились сыграть в свою любимую игру. Игра проходит по следующим правилам. У игроков есть ориентированный граф с n вершинами и m рёбрами, в одной из вершин которого стоит фишка. Изначально она находится в вершине s. Игроки по очереди перемещают фишку, за каждый ход передвигая её вдоль ребра графа. Первым ходит Петя. Игрок, который не может совершить ход, проигрывает. Если игра продолжается 106 ходов, объявляется ничья.
В ночь перед игрой Васе нужно было выполнить большую лабораторную работу по предмету «Орфография и части речи», поэтому, как только началась игра, он уснул. Петя решил воспользоваться ситуацией и делать ходы как за себя, так и за Васю.
Помогите Пете понять, может ли он выиграть, или хотя бы сыграть вничью.
В первой строке входных данных содержатся два целых числа n и m — число вершин и число рёбер в графе соответственно (2 ≤ n ≤ 105, 0 ≤ m ≤ 2·105).
В следующих n строках содержится информация о рёбрах графа. В i-й строке (1 ≤ i ≤ n) записано целое неотрицательное число ci — количество вершин, в которые есть рёбра из вершины i, а затем ci различных целых чисел ai, j — номера этих вершин (1 ≤ ai, j ≤ n, ai, j ≠ i).
Гарантируется, что сумма всех ci равна m.
В следующей строке содержится номер вершины s — изначальной позиции фишки (1 ≤ s ≤ n).
Если Петя может выиграть, в первой строке выведите «Win». В следующей строке выведите числа v1, v2, ..., vk (1 ≤ k ≤ 106) — последовательность вершин, которые должен посетить Петя для победы. Вершина v1 должна совпадать с s. Для i = 1... k - 1 в графе должно быть ребро из вершины vi в вершину vi + 1. Последовательность должна быть такова, что из вершины vk нет хода, и при такой игре проигрывает именно Вася, а не Петя.
Если Петя не может выиграть, но может сыграть вничью, в единственной строке выведите «Draw». Иначе выведите «Lose».
5 6
2 2 3
2 4 5
1 4
1 5
0
1
Win
1 2 4 5
3 2
1 3
1 1
0
2
Lose
2 2
1 2
1 1
1
Draw
В первом примере игра происходит на следующем графе:
Изначально фишка находится в вершине 1. Первым ходом Петя передвигает фишку в вершину 2, затем он ходит за Васю в вершину 4. После чего опять за себя в вершину 5. Теперь ход Васи, но ему некуда ходить, поэтому Петя выиграл.
Во втором примере игра происходит на следующем графе:
Изначально фишка находится в вершине 2. Петя может сходить только в вершину 1. После этого он вынужден сходить за Васю в вершину 3. Теперь ход Пети, но ему некуда ходить, поэтому Петя проиграл.
В третьем примере игра происходит на следующем графе:
Петя не может выиграть, но может совершать ходы по циклу, поэтому партия закончится вничью.
