Double move

Alice and Bob are playing a game with the help of Samantha. There are $n$ stones, numbered from $1$ to $n$. The game unfolds in three phases.

**Phase One:** Alice and Bob take turns making declarations, with Alice going first. During each turn, a player declares their intention to take a stone by naming two options. These options can be the same, and players can mention stones that have already been declared in previous turns. No stones are actually taken in this phase; players are merely setting up their intentions for the next phase. This phase concludes after $n+1$ declarations.

For example, if $n=3$, the first phase might look like this:

1. Alice: "I will take either stone 1 or stone 3."

2. Bob: "I will take either stone 2 or stone 2."

3. Alice: "I will take either stone 3 or stone 2."

4. Bob: "I will take either stone 1 or stone 3."

**Phase Two:** Samantha selects one of the two options for each of the $n+1$ declarations, choosing either "first" or "second." Each sequence of $n+1$ choices by Samantha is called a scenario. There are $2^{n+1}$ possible scenarios, as each declaration offers two choices. Even if the options are identical, both "first" and "second" choices are considered to create different scenarios.

For instance, one possible scenario for the example above is:

1. "First": Alice will take the first stone.

2. "First": Bob will take the second stone.

3. "Second": Alice will take the second stone.

4. "First": Bob will take the first stone.

**Phase Three:** Alice and Bob start taking stones based on Samantha's decisions. The first player unable to take the required stone—because it has already been taken—loses the game. Since there are $n$ stones and $n+1$ moves, one player will inevitably lose.

In the example, Alice takes the first stone, Bob takes the second, and when Alice tries to take the second stone again, she finds it already taken. Thus, Alice loses, and Bob wins.

You are given the number $n$ and the current state of the game during the first phase: a sequence of $k$ declarations already made. These declarations can be arbitrary.

From this point, Alice and Bob will play optimally, aiming to minimize the number of scenarios in which they lose, knowing Samantha will choose each scenario with equal probability.

Assuming Alice and Bob continue the game optimally, determine the number of scenarios in which each player wins.

Input

The first line contains two 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.

The next $k$ lines list the declarations in order. Each line contains two integers representing the stones (both between $1$ and $n$, not necessarily distinct).

If $k<n+1$, the next player to declare depends on whether $k$ is even or odd.

Output

Output two numbers: the number of scenarios in which Alice wins and the number of scenarios in which Bob wins, assuming both play optimally.

The sum of these two numbers should be $2^{n+1}$.

Examples

Note

The first example matches the problem statement. No further declarations are needed, so we only need to determine how many of Samantha's possible decisions result in Alice winning and how many result in Bob winning. Alice wins if Samantha selects 1 for her first move and 3 for her second move; she loses in all other cases.

In the second example, if Alice begins with "1 1" and Bob follows with "2 2," Alice will lose regardless of her third move because Samantha will have to choose the first stone on the first move and the second stone on the second move, leaving no stones for Alice's third move. However, this is not Alice's optimal first move. Instead, she should start with "1 2." Then, no matter what Bob does on the second move or Alice on the third, each will win in 4 out of 8 scenarios.

Scoring

Block 1 (15 points): $n\le 4$.

Block 2 (34 points): $n\le 10$.

Block 3 (20 points): $n\le 25$.

Block 4 (10 points): $k=0$.

Block 5 (21 points): no additional constraints.