{"raw_statement":[{"iden":"background","content":"PA 2024 4B"},{"iden":"statement","content":"**题目译自 [PA 2024](https://sio2.mimuw.edu.pl/c/pa-2024-1/dashboard/) Runda 4 [Desant 3](https://sio2.mimuw.edu.pl/c/pa-2024-1/p/des/)，感谢 Macaronlin 提供翻译**\n\n$n$ 个士兵，从左到右编号为 $1$ 到 $n$。每个士兵有两种状态：准备好和未准备好。现对这些士兵下发 $m$ 条命令，第 $i$ 条命令会使得在 $a_i$ 位置和 $b_i$ 位置的士兵交换位置，但只有 $a_i$ 位置的士兵准备好并且 $b_i$ 位置的士兵没有准备好时才能交换，否则无效。\n\n问对于 $1$ 到 $n$ 中的每个整数 $k$，考虑 $\\binom{n}{k}$ 种士兵的初始准备情况，其中有 $k$ 个士兵已准备好，求有多少种准备情况可以在进行 $m$ 条命令后，满足所有准备好的士兵形成一段连续区间。你只需要输出种类数对 $2$ 取模后的值即可。"},{"iden":"input","content":"第一行两个整数 $n$ 和 $m\\ (2\\le n\\le 35,1\\le m\\le 1\\,000)$，分别表示士兵数和命令数。\n\n接下来 $m$ 行，每行两个整数 $a_i$ 和 $b_i\\ (1\\le a_i,b_i\\le n,a_i\\neq b_i)$，描述一条命令。"},{"iden":"output","content":"输出一行 $n$ 个整数，其中第 $k$ 个整数表示有 $k$ 个士兵准备好的所有初始情况中，可以在进行 $m$ 条命令后使得所有准备好的士兵形成一段连续区间的情况数。输出对 $2$ 取模。"},{"iden":"note","content":"如果一开始只有一名士兵准备好，那么无论如何操作，最终准备好的士兵一定形成一个连续的区间。\n\n考虑这样一种情况：除了队列中的第二名士兵外，其他士兵都已准备好。第一个命令不会影响士兵的位置。第二道命令下达后，由于队列中的第一名士兵已准备好，而第二名士兵尚未准备好，他们将交换位置。第三道命令同样没有影响。由于现在队列中的第一名士兵还没有准备好，而队列中的第四名士兵已经准备好，因此他们不会因为最后一道命令而交换位置。最终只有排在第一位的士兵没有准备好。这是 $k = 3$ 时唯一一种满足条件的初始情况。\n\n未取模前的答案为 $[4,0,1,1]$。"}],"translated_statement":null,"sample_group":[["4 4\n4 1\n1 2\n3 4\n1 4\n","0 0 1 1\n"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}