Background

Day 2 Problem D.

The statement is translated from EGOI2021 doublemove.

Problem Description

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

In the first phase, Alice and Bob take turns, with Alice going first. In each turn, a player announces which stone they are going to take, but they do not directly specify a single stone. Instead, they give two options. The two options may be the same. They may also mention stones that have already been mentioned before. No stones are taken in the first phase—the players only announce their intentions for the second phase. The first phase ends after $n+1$ announcements.

Here is an example of the first phase when $n=3$:

1. Alice: “I will take $1$ or $3$.”
2. Bob: “I will take $2$ or $2$.”
3. Alice: “I will take $3$ or $2$.”
4. Bob: “I will take $1$ or $3$.”

In the second phase, for each of the $n+1$ announcements, Claire chooses one of the two options by saying “former” or “latter”. We call the sequence of Claire’s $n+1$ choices a plan. It can be seen that there are exactly $2\cdot 2\cdot 2\cdot\cdots\cdot 2=2^{n+1}$ possible plans. (Even if in some announcements the two options are exactly the same, we still consider choosing “former” and choosing “latter” as different plans.)

Here is one of the $16$ possible plans that Claire might choose:

1. “Former”: Alice will take $1$.
2. “Former”: Bob will take $2$.
3. “Latter”: Alice will take $2$.
4. “Former”: Bob will take $1$.

In the third phase, Alice and Bob start taking stones according to Claire’s choices. The first player who cannot perform their required move—because that stone has already been taken—loses the game. Note that there are $n$ stones and $n+1$ moves, so one player will inevitably lose in the end.

In the example above, Alice first takes $1$. Bob then takes $2$. Alice wants to take $2$ next, but it has already been taken, so Alice loses and Bob wins.

You are given the integer $n$, and the game state at some moment during the first phase: a sequence of $k$ announcements that have already been made. These announcements may be completely arbitrary.

From this point on, Alice and Bob will play optimally, meaning:

No matter how Alice and Bob play, Claire chooses uniformly at random from the $2^{n+1}$ possible plans. Alice and Bob know this, so when they play optimally, each of them tries to minimize the number of plans in which they lose.

Assuming Alice and Bob continue the game as described above, compute, for each of them, the number of plans under which they win the game.

Input Format

The first line contains two integers $n,k$: the number of stones and the number of announcements already made.

The next $k$ lines describe the announcements in order. Each line contains two integers: the indices of the two stones (in $1\sim n$ and not necessarily distinct).

Note that when $k < n+1$, the player to make the next announcement is determined by the parity of $k$.

Output Format

Print one line with two integers: the number of plans in which Alice wins, and the number of plans in which Bob wins, assuming both continue the game optimally as described above.

Note that the sum of these two integers should be $2^{n+1}$.

3 4
1 3
2 2
3 2
1 3

4 12

2 0

4 4

Hint

Explanation for Sample $1$.

This sample is the same as the one given in the Description. No further announcements need to be made, so we only need to count how many plans make Alice win and how many plans make Bob win. Alice wins if and only if Claire chooses $1$ in the first step, and chooses $3$ in the third step. All other plans make Alice lose.

Explanation for Sample $2$.

If Alice first announces $(1,1)$, Bob will announce $(2,2)$. No matter what Alice announces next, she will lose, because Claire will choose $1$ in the first step and $2$ in the second step, and then there will be no remaining stone for Alice to take in the third step. However, this is not Alice’s optimal first move: she should instead announce $(1,2)$ first. Then, no matter how Bob and Alice announce in the last two steps, they will each win $4$ out of the $8$ plans.

Constraints

For all data, $1\le n\le 35$, $0\le k\le n+1$.

• Subtask 1 ($15$ points): $n\le 4$.
• Subtask 2 ($34$ points): $n\le 10$.
• Subtask 3 ($20$ points): $n\le 25$.
• Subtask 4 ($10$ points): $k=0$.
• Subtask 5 ($21$ points): no additional constraints.

Translated by ChatGPT 5