{"raw_statement":[{"iden":"background","content":"Day 2 Problem D.\n\n题面译自 [EGOI2021 doublemove](https://stats.egoi.org/media/task_description/2021_doublemove_en.pdf)。"},{"iden":"statement","content":"爱丽丝和鲍勃在玩游戏，克莱尔在帮助他们。共有 $n$ 颗石子，编号从 $1$ 到 $n$。游戏分为三个阶段。\n\n在第一阶段，爱丽丝和鲍勃轮流操作，爱丽丝先手。在每次操作中，玩家宣布他们要拿的石头，但不直接说出拿哪一个，而是给出两个选项。两个选项可能是相同的。也有可能说出已经说过的石头。第一阶段不取石子——玩家只是宣布他们在第二阶段的意图。第一阶段在宣布 $n+1$ 次后结束。\n\n下面是 $n=3$ 的第一阶段的例子：\n\n1. 爱丽丝：“我会取走 $1$ 或 $3$”\n2. 鲍勃：“我会取走 $2$ 或 $2$”\n3. 爱丽丝：“我会取走 $3$ 或 $2$”\n4. 鲍勃：“我会取走 $1$ 或 $3$”\n\n在第二阶段，对于 $n+1$ 次宣布的每一个，克莱尔用说“前者”或“后者”的方式从两个选项中选择一个。我们称克莱尔做出的 $n+1$ 次选择的序列为一个*方案*。可以发现，恰好有 $2\\cdot 2\\cdot 2\\cdot\\cdots\\cdot 2=2^{n+1}$ 种可能的方案。（即使在一些宣布中，两个选项是完全相同的，我们认为“前者”“后者”选择不同为不同的方案。）\n\n下面是克莱尔可能选择的 $16$ 种方案之一：\n\n1. “前者”：爱丽丝将取 $1$。\n2. “前者”：鲍勃将取 $2$。\n3. “后者”：爱丽丝将取 $2$。\n4. “前者”：鲍勃将取 $1$。\n\n在第三阶段，爱丽丝和鲍勃根据克莱尔的选择开始取石子。第一个无法做出要求的操作的人——因为那个石子已经被取走——输掉游戏。注意到有 $n$ 个石子和 $n+1$ 次操作，一个玩家必然最终输掉游戏。\n\n在上面的例子中，爱丽丝先取走 $1$。鲍勃接着取走 $2$。爱丽丝希望继续取走 $2$，但它已经被取走了，所以爱丽丝输掉了游戏，鲍勃因此获胜。\n\n你已知整数 $n$，和第一阶段某一时刻的游戏状态：一个长度为 $k$ 的已经做出的宣布序列。这些宣布可以是完全随意的。\n\n从此时开始，爱丽丝和鲍勃会以最优方式玩游戏，也就是说：\n\n无论爱丽丝和鲍勃怎么玩，克莱尔都均匀随机地从 $2^{n+1}$ 种可能的方案中选择一个。爱丽丝和鲍勃知道这一点，因此当以最优方式玩游戏时，他们都尽力最小化他们输的方案数。\n\n假设爱丽丝和鲍勃会按照上面描述的方式继续游戏。请分别求出两个人赢得游戏的方案数。"},{"iden":"input","content":"第一行两个整数 $n,k$：石头数和已经做出的宣布数。\n\n接下来 $k$ 行，每行按照顺序描述一次宣布。每行两个整数：两个石头的编号（在 $1\\sim n$ 且不一定不同）。\n\n注意到当 $k < n+1$ 时，下一个做出宣布的玩家由 $k$ 的奇偶性决定。"},{"iden":"output","content":"一行，两个整数：爱丽丝赢的方案数、鲍勃赢的方案数，假设他们都按照上面描述的方式继续玩游戏。\n\n注意到这两个整数的和应当为 $2^{n+1}$。"},{"iden":"note","content":"**样例 $1$ 解释**\n\n这个样例与【题目描述】中给出的相同。不需要做出更多的宣布了，因此我们只需要计算多少种方案会导致爱丽丝赢，多少种方案会导致鲍勃赢。爱丽丝赢当且仅当克莱尔在第一步选择了 $1$，且在第三步选择了 $3$。其他方案都会导致爱丽丝输。\n\n---\n\n**样例 $2$ 解释**\n\n如果爱丽丝先宣布 $(1,1)$，鲍勃会宣布 $(2,2)$，无论爱丽丝接下来宣布什么，她都会输，因为克莱尔会在第一步选择 $1$，在第二步选择 $2$，第三步就没有剩下的石头给爱丽丝取了。然而，这不是爱丽丝第一步的最优方案：她应该首先宣布 $(1,2)$。然后，无论鲍勃和爱丽丝在后两步如何宣布，他们都会赢 $8$ 种方案中的 $4$ 种。\n\n---\n\n**数据范围**\n\n对于全部数据，$1\\le n\\le 35$，$0\\le k\\le n+1$。\n\n- 子任务一（$15$ 分）：$n\\le 4$。\n- 子任务二（$34$ 分）：$n\\le 10$。\n- 子任务三（$20$ 分）：$n\\le 25$。\n- 子任务四（$10$ 分）：$k=0$。\n- 子任务五（$21$ 分）：无特殊限制。"}],"translated_statement":null,"sample_group":[["3 4\n1 3\n2 2\n3 2\n1 3","4 12"],["2 0","4 4"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}