Двочасткова гра
Обмеження: 2 сек., 256 МіБ
Дано двочастковий граф, Зеник і Марічка грають у гру на ньому. За один хід можна провести ребро, так щоб граф надалі лишався двочастковим. Хто не зможе зробити хід — програє. Хто виграє при правильній грі обох суперників, якщо Марічка починає?
Зверніть увагу, що граф не може містити мультиребер в жоден момент часу.
Вхідні дані
У першому рядку задано єдине ціле число \(t\) — кількість тестів, які потрібно розв’язати.
Далі йде опис кожного тесту, у першому рядку два цілі числа через пробіл — \(n\) та \(m\).
У наступних \(m\) рядках задано по два цілі числа \(u\) та \(v\) — ребра графу.
Вихідні дані
Для кожного тесту виведіть єдиний рядок Marichka, якщо
виграє Марічка, та Zenyk в іншому випадку.
Обмеження
\(1 \le t \le 10^4\),
\(1 \le n \le 10^5\),
\(0 \le m \le 10^5\),
\(1 \le u, v \le n\),
заданий граф гарантовано двочастковий,
cума m по всіх тестах не перевищує \(10^6\).
Приклади
| Вхідні дані (stdin) | Вихідні дані (stdout) |
|---|---|
| 3 4 1 2 4 4 3 1 2 1 3 1 4 2 0 | Marichka Zenyk Marichka |
| Element Type | Створено | Хто | Задача | Компілятор | Результат | Час (сек.) | Пам'ять (МіБ) | № | Дії |
|---|