题目背景

实验室里有一排 $n$ 个开关，每个开关只有两种状态：关闭记为 $0$，开启记为 $1$。

接下来，系统会按照给定顺序执行 $m$ 条指令。每条指令会观察两个不同位置 $u,v$：如果第 $u$ 个开关当前为 $1$，且第 $v$ 个开关当前为 $0$，系统就交换这两个位置的状态；否则什么也不做。

你需要研究所有可能的初始状态。

题目描述

给定 $n,m$ 以及 $m$ 条指令。对于每一个 $k=1,2,\\ldots,n$，考虑所有恰好有 $k$ 个位置为 $1$ 的初始 $01$ 序列。

依次执行全部 $m$ 条指令后，如果最终序列中所有 $1$ 所在的位置构成一个连续区间，则称这个初始状态是好的。

请你对每个 $k$，求出好的初始状态数量对 $2$ 取模后的结果。

输入格式

第一行包含两个正整数 $n,m$。

接下来 $m$ 行，每行包含两个正整数 $u,v$，表示一条指令。

输出格式

输出 $n$ 个整数，第 $i$ 个整数表示 $k=i$ 时的答案，对 $2$ 取模。

样例 0 输入

4 4
4 1
1 2
3 4
1 4

样例 0 输出

0 0 1 1

样例 0 解释

取模前，$k=1,2,3,4$ 的答案分别为：

$$4,0,1,1.$$

例如初始序列为 $1011$ 时，执行过程为：

$$1011 \rightarrow 1011 \rightarrow 0111 \rightarrow 0111 \rightarrow 0111.$$

最终所有 $1$ 构成连续区间。

附加样例

• 样例 1 见下发文件中的 ex_polygon1.in/out，该样例满足子任务 $2$ 的限制。
• 样例 2 见下发文件中的 ex_polygon2.in/out，该样例满足子任务 $4$ 的限制。
• 样例 3 见下发文件中的 ex_polygon3.in/out，该样例满足子任务 $8$ 的限制。

数据范围与约定

对于所有测试数据，保证：

$$1 \le n \le 35,\qquad 1 \le m \le 1000,$$

且每条指令满足：

$$1 \le u,v \le n,\qquad u\ne v.$$

子任务	特殊性质	分值
$1$	$n\le 7,\ m\le 100$	$10$
$2$	$n\le 15,\ m\le 200$
$3$	$n\le 20,\ m\le 200$
$4$	$n\le 22,\ m\le 300$	$8$
$5$	$n\le 24,\ m\le 500$
$6$	$n\le 26,\ m\le 600$
$7$	$n\le 29,\ m\le 800$
$8$	$n\le 30,\ m\le 100$，每条指令的 $(u,v)$ 在所有可能的有序二元组中均匀随机选择	$25$
$9$	$n\le 34,\ m\le 900$	$8$
$10$	无特殊限制	$5$