Double Move

Alice and Bob are playing a game, and Claire is helping them. There are stones, numbered from $1$ to $n$. The game consists of three phases.

In the first phase, Alice and Bob make alternating moves. Alice moves first. In each move, a player declares their intention to take a stone, but instead of naming the stone, they name two options. The two options may be the same. A player may also name stones that were already named in earlier moves. No stones are actually taken in this phase. The first phase ends when $n+1$ declarations have been made.

In the second phase, Claire picks one of the two options in each of the $n+1$ declarations by saying "first" or "second". Each sequence of $n+1$ choices made by Claire is a scenario. There are exactly $2^{n+1}$ scenarios. Even when the two options in a declaration are the same, choosing "first" and choosing "second" count as different scenarios.

In the third phase, Alice and Bob take stones according to Claire's choices. The first player who cannot make the required move, because the stone is already taken, loses the game. Since there are $n$ stones and $n+1$ moves, one of the players must lose.

Alice and Bob know that Claire picks each of the $2^{n+1}$ scenarios with equal probability. When playing optimally, each player tries to minimize the number of scenarios in which they lose.

You are given $n$ and the state of the game partway through the first phase: a sequence of $k$ declarations that have already been made. These declarations can be arbitrary. From this point on, Alice and Bob play optimally as described above. For each player, find the number of scenarios in which that player wins.

The first line contains two space-separated integers $n$ and $k$ ($1 \le n \le 35$, $0 \le k \le n+1$): the number of stones and the number of declarations already made.

Each of the next $k$ lines contains two space-separated integers, the numbers of the two stones in one declaration, in the order they were made. Both numbers are between $1$ and $n$, inclusive, and they need not be distinct.

When $k < n+1$, the parity of $k$ determines which player makes the next declaration.

Print one line with two space-separated integers: the number of scenarios in which Alice wins and the number of scenarios in which Bob wins, assuming both players play the rest of the game optimally. The sum of the two numbers must equal $2^{n+1}$.

The first sample matches the example in the statement. No declarations remain, so we only count Claire's choices that lead to an Alice win and to a Bob win. Alice wins if Claire picks stone $1$ for her first move and stone $3$ for her second move, and loses in all other cases.

In the second example, if Alice starts by declaring "1 1", Bob answers "2 2", and whatever Alice declares third, she loses. Claire can pick stone $1$ for the first move and stone $2$ for the second, leaving no stone for Alice's third move. This is not Alice's best opening. She should declare "1 2" instead. Then, no matter how Bob and Alice play afterward, each of them wins in $4$ of the $8$ scenarios.