Двочасткова гра

Обмеження: 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\).

Приклади