Двойной ход

Алиса и Боб играют в игру, в которой им помогает Саманта. У них есть $n$ камней, пронумерованных от $1$ до $n$. Игра состоит из трех этапов.

На первом этапе Алиса и Боб поочередно делают ходы, начиная с Алисы. Каждый ход игрок называет два варианта камней, которые он хотел бы взять. Эти варианты могут совпадать, и можно называть камни, которые уже были упомянуты ранее. На этом этапе камни фактически не берутся — игроки лишь заявляют о своих намерениях на второй этап. Первый этап завершается после $n+1$ заявлений.

Пример первой фазы для $n=3$:

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

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

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

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

На втором этапе Саманта для каждого из $n+1$ заявлений выбирает один из двух вариантов, говоря «первый» или «второй». Каждая последовательность из $n+1$ выборов Саманты называется сценарием. Всего существует $2^{n+1}$ возможных сценариев. Даже если в заявлении оба варианта одинаковы, выбор «первый» или «второй» все равно создает разные сценарии.

Пример одного из 16 сценариев для вышеупомянутого случая:

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

2. «Первый»: Боб выберет второй камень

3. «Второй»: Алиса выберет второй камень

4. «Первый»: Боб выберет первый камень

На третьем этапе Алиса и Боб начинают брать камни в соответствии с решениями Саманты. Игрок, который не может взять камень, так как он уже занят, проигрывает. Поскольку камней $n$, а ходов $n+1$, один из игроков обязательно проиграет.

В приведенном примере Алиса берет первый камень, затем Боб берет второй. Алиса должна взять второй камень, но он уже занят, поэтому она проигрывает, а Боб выигрывает.

Вам дано число $n$ и текущее состояние игры на первом этапе: последовательность из $k$ заявлений. Эти заявления могут быть любыми.

С этого момента Алиса и Боб будут играть оптимально, как описано далее.

Независимо от действий Алисы и Боба, Саманта выбирает каждый из возможных сценариев с равной вероятностью. Зная это, Алиса и Боб стремятся минимизировать количество сценариев, в которых они проигрывают.

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

Входные данные

Первая строка содержит два целых числа $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 балл): без дополнительных ограничений.