Подвійний хід

Аліса та Боб грають у гру, а Саманта їм допомагає. Є $n$ каменів, пронумерованих від $1$ до $n$. Гра складається з трьох фаз.

На першому етапі Аліса та Боб роблять ходи по черзі. Аліса робить хід першою. На кожному ході гравець заявляє про свій намір взяти камінь, але замість того, щоб сказати, який саме, він називає два варіанти. Ці два варіанти можуть бути однаковими. Також можна назвати камені, які вже були названі в попередніх ходах. На першій фазі фактично не беруть каміння - гравці просто заявляють про свої наміри щодо другої фази. Перший етап закінчується, коли вже зробили $n+1$ тверджень.

Ось приклад першої фази для $n=3$:

1. Аліса: «Я візьму або камінь 1, або камінь 3»

2. Боб: «Я візьму або камінь 2, або камінь 2»

3. Аліса: «Я візьму або камінь 3, або камінь 2»

4. Боб: «Я візьму або камінь 1, або камінь 3»

На другій фазі, для кожної з $n+1$ тверджень, які були зроблені, Саманта вибирає один із двох варіантів, кажучи «перший» або «другий». Назвемо сценарієм кожну послідовність з $n+1$ варіантів, зроблених Самантою. Зверніть увагу, що існує рівно $2\cdot 2\cdot 2\cdot \cdots \cdot 2=2^{n+1}$ можливих сценаріїв. (Навіть якщо в якомусь твердженні перший і другий варіанти однакові, ми розглядаємо можливість вибрати варіант «перший» або «другий», щоб отримати різні сценарії.)

Ось один із 16 сценаріїв, які Саманта могла вибрати у наведеному вище прикладі:

1. «Перший»: Аліса вибере перший камінь

2. «Перший»: Боб вибере другий камінь

3. «Другий»: Аліса вибере другий камінь

4. «Перший»: Боб вибере перший камінь

І на третьому етапі Аліса та Боб фактично починають брати каміння відповідно до рішень Саманти. Перший гравець, який не може зробити необхідний хід — оскільки відповідний камінь уже взятий, програє гру. Зверніть увагу, що оскільки є $n$ каменів і $n+1$ ходів, один із гравців повинен врешті програти.

У наведеному вище прикладі Аліса починає з того, що фактично візьме перший камінь. Боб потім візьме другий камінь. Алісі потрібно буде взяти другий камінь, проте його вже взяли. Тому Аліса програє, а Боб виграє.

Вам дається число $n$ і стан гри в певний момент на першому етапі: послідовність з $k$ тверджень, які вже були зроблені. Ці заяви можуть бути абсолютно довільними.

З цього моменту Аліса та Боб будуть грати в гру оптимально, як описано у наступному параграфі.

Незалежно від того, як грають Аліса та Боб, Саманта однаково ймовірно вибере кожен із можливих сценаріїв із$2^{n+1}$. Аліса та Боб це знають, і тому, граючи оптимально, вони обидва намагаються мінімізувати кількість сценаріїв, в яких програють.

Припустимо, Аліса та Боб будуть грати решту гри, як описано вище. Для кожного з двох гравців знайдіть кількість сценаріїв, в яких вони виграють гру.

Вхідні дані

Перший рядок містить два цілі числа $n$ та $k$ ($1\le n\le 35$, $0\le k\le n+1$) — кількість каменів та кількість тверджень, які вже зроблені.

Наступні $k$ рядків описують твердження у тому порядку, у якому вони були зроблені. Кожен з наступних рядків містить два цілі числа — номери каменів (обидва від $1$ до $n$ включно, вони не обов'язково різні).

Зверніть увагу, що якщо $k<n+1$, то наступний гравець, який зробить твердження, залежить від парності $k$.

Вихідні дані

Виведіть два числа: кількість сценаріїв, в яких Аліса виграє, і кількість сценаріїв, в яких Боб виграє, припускаючи, що обидва гравці грають решту гри, як описано вище.

Зверніть увагу, що сума двох виведених чисел повинна дорівнювати $2^{n+1}$.

Приклади

Примітка

Перший приклад відповідає прикладу з умови задачі. Твердження більше не потрібно робити, тому нам просто потрібно побачити, скільки можливих рішень Саманти призводить до перемоги Аліси, а скільки з них — до перемоги Боба. Аліса виграє, якщо Саманта підбере їй $1$ на першому ході, і $3$ на другому ході, і програє у всіх інших випадках.

У другому прикладі, якщо Аліса почне з твердження «1 1», Боб продовжить «2 2», то яке б твердження Аліса не зробила б на третьому ході - вона програє, оскільки Саманті доведеться вибрати перший камінь на першому ході й другий камінь на другому ході, і для третього ходу Аліси каміння не залишиться. Однак це не оптимальний перший крок для Аліси: натомість вона повинна почати з твердження «1 2». Тоді, незалежно від того, що робить Боб на другому ході й що робить Аліса на третьому, кожен із них виграє у $4$ випадках із $8$.

Оцінювання

Блок 1 (15 балів): $n\le 4$.

Блок 2 (34 бали): $n\le 10$.

Блок 3 (20 балів): $n\le 25$.

Блок 4 (10 балів): $k=0$.

Блок 5 (21 бал): без додаткових обмежень.