题目描述

题目译自 European Girls' Olympiad in Informatics 2021 Day2 T4. Double Move

爱丽丝和鲍勃正在玩一个游戏，克莱尔在协助他们。游戏中有 $n$ 块编号从 $1$ 到 $n$ 的石头，游戏分为三个阶段。

第一阶段，爱丽丝和鲍勃轮流行动，爱丽丝先开始。每轮行动中，玩家宣布他们打算拿一块石头，但不是直接指定哪一块，而是给出两个选项。两个选项可以相同，也可以是之前行动中提到过的石头。在这个阶段，石头不会被实际拿走——玩家只是为第二阶段声明意图。第一阶段在进行 $n+1$ 次声明后结束。

例如，当 $n=3$ 时，第一阶段可能如下：

• 爱丽丝：「我要拿石头 $1$ 或石头 $3$。」
• 鲍勃：「我要拿石头 $2$ 或石头 $2$。」
• 爱丽丝：「我要拿石头 $3$ 或石头 $2$。」
• 鲍勃：「我要拿石头 $1$ 或石头 $3$。」

第二阶段，对于已进行的 $n+1$ 次声明，克莱尔逐一选择每个声明的两个选项之一，宣布拿「第一个」或「第二个」。我们将克莱尔做出的 $n+1$ 次选择序列称为一个场景。总共有 $2 \cdot 2 \cdot \ldots \cdot 2 = 2^{n+1}$ 种可能的场景。（即使某个声明的两个选项相同，选择「第一个」或「第二个」仍被视为不同场景。）

以上例为例，克莱尔可能选择以下一个场景（共 $16$ 种场景之一）：

• 「第一个」：爱丽丝拿石头 $1$。
• 「第一个」：鲍勃拿石头 $2$。
• 「第二个」：爱丽丝拿石头 $2$。
• 「第一个」：鲍勃拿石头 $1$。

第三阶段，爱丽丝和鲍勃根据克莱尔的决定开始实际拿石头。第一个无法执行所需行动的玩家——因为对应的石头已被拿走——将输掉游戏。注意，由于有 $n$ 块石头但需进行 $n+1$ 次行动，必然有一个玩家会输。

在上述例子中，爱丽丝先拿石头 $1$，鲍勃接着拿石头 $2$。爱丽丝想继续拿石头 $2$，但它已被拿走，因此爱丽丝输，鲍勃赢。

你将得到石头数量 $n$ 以及第一阶段中某时刻的游戏状态：已经进行了 $k$ 次声明的序列。这些声明可以完全任意。

从此刻起，爱丽丝和鲍勃将以最优策略继续游戏，如下所述：

无论爱丽丝和鲍勃如何行动，克莱尔对 $2^{n+1}$ 种场景的选择概率均等。爱丽丝和鲍勃知道这一点，因此在最优策略下，他们都试图最小化自己输掉的场景数量。

假设爱丽丝和鲍勃按上述方式继续游戏，你的任务是为两位玩家分别找出他们赢得游戏的场景数量。

输入格式

第一行包含两个用空格分隔的整数 $n,k$ ($1 \leq n \leq 35$, $0 \leq k \leq n+1$)，分别表示石头数量和已经进行的声明次数。

接下来的 $k$ 行，每行描述一次声明，按声明顺序给出。每行包含两个用空格分隔的整数，表示两个石头编号（均在 $1$ 到 $n$ 之间，可能相同）。

注意，当 $k < n+1$ 时，下一个进行声明的玩家取决于 $k$ 的奇偶性。

输出格式

输出一行，包含两个用空格分隔的整数：假设两位玩家按题目描述继续游戏，爱丽丝赢得的场景数量和鲍勃赢得的场景数量。

注意，你输出的两个数字之和必须等于 $2^{n+1}$。

样例 1

输入

3 4
1 3
2 2
3 2
1 3

输出

4 12

对应题目描述中的例子。此时不再需要进行声明，只需计算克莱尔可能的决定中有多少导致爱丽丝获胜，多少导致鲍勃获胜。爱丽丝会在克莱尔为她第一次选择石头 $1$ 且第二次选择石头 $3$ 时获胜，其他情况下输。

样例 2

输入

2 0

输出

4 4

如果爱丽丝以声明 $1\ 1$ 开始，鲍勃会继续声明 $2\ 2$，无论爱丽丝第三次声明什么，她都会输，因为克莱尔将为第一次选择石头 $1$，为第二次选择石头 $2$，第三次没有石头留给爱丽丝。然而，这不是爱丽丝的最优开局：她应该以 $1\ 2$ 开始。之后，无论鲍勃第二次做什么，爱丽丝第三次做什么，他们各自在 $8$ 种情况中各赢 $4$ 次。

数据范围与提示

详细子任务附加限制及分值如下表所示。

子任务	分值	附加限制
1	$15$	$n \leq 4$
2	$34$	$n \leq 10$
3	$20$	$n \leq 25$
4	$10$	$k=0$
5	$21$	无附加限制