バイトツィアは再びビトツィアへの攻撃を計画しています。精鋭特殊部隊「バイトグロム」には $n$ 人の兵士が所属しており、今朝の集合では一列に並んでいました。降下作戦の責任者であるバイトザール将軍は、彼らの位置を左から右へ $1$ から $n$ までの番号で割り当てました。

各兵士は、降下作戦の準備ができているか、あるいは法改正に伴う追加訓練が必要な状態のいずれかです。バイトザール将軍は、降下準備ができているすべての兵士が列の中で連続した区間を形成することを望んでいます。より厳密には、兵士の配置において $1 \le i < j < k \le n$ を満たす $3$ つの位置が存在し、$i$ 番目と $k$ 番目の兵士が準備完了で、$j$ 番目の兵士が準備完了でないという状況がないことを望んでいます。

この条件はデフォルトでは満たされない可能性があるため、バイトザールは $m$ 個の命令を発行します。$i$ 番目の命令では、位置 $a_i$ と $b_i$ にいる兵士に対し、位置を入れ替えるよう命じます。兵士たちは、$a_i$ 番目の兵士が準備完了であり、かつ $b_i$ 番目の兵士が準備完了でない場合にのみ、位置を入れ替えます。

バイトザールはすでに一連の命令を選択しており、それを実行するつもりです。しかし、彼は何人の兵士が準備完了であるか、また彼らがどの位置にいるのかを知りません。したがって、彼は $1$ から $n$ までの各整数 $k$ について、次の問題を解決したいと考えています。降下準備ができている兵士がちょうど $k$ 人であるような、考えられるすべての $\binom{n}{k}$ 通りの初期配置を考えます。これらの配置のうち、すべての命令を実行した後にバイトザールの条件が満たされる（すなわち、準備完了の兵士が列の中で連続した区間を形成する）ものはいくつあるでしょうか。彼を助け、求める値を計算してください。

注記：本コンテストには多くの初心者が参加しているため、大きな数で皆さんを悩ませないことにしました。したがって、各 $k$ について、可能性の数を $2$ で割った余りを答えるだけで十分です。

入力

入力の最初の行には、2 つの整数 $n$ と $m$ ($2 \le n \le 35; 1 \le m \le 1\,000$) が含まれており、それぞれ列に並んだ兵士の数と命令の数を表します。

続く $m$ 行には命令の記述が含まれています。$i$ 番目の行には、問題文で説明されている 2 つの整数 $a_i$ と $b_i$ ($1 \le a_i, b_i \le n; a_i \neq b_i$) が含まれています。

出力

出力の唯一の行には、空白で区切られた $n$ 個の整数が含まれている必要があります。$k$ 番目の整数は、降下準備ができている兵士がちょうど $k$ 人であり、かつすべての命令を実行した後に準備完了の兵士が連続した区間を形成するような初期配置の数を $2$ で割った余りと等しくなければなりません。

入出力例

入力 1

4 4
4 1
1 2
3 4
1 4

出力 1

0 0 1 1

注記

例の解説：もし最初に準備完了の兵士が $1$ 人だけであれば、その兵士は確実に（要素数 $1$ の）連続した区間を形成します。一方で、準備完了の兵士が $2$ 人いて、最終的に彼らが隣り合うような状況は存在しません。

列の $2$ 番目の兵士以外全員が準備完了である状況を考えます。最初の命令は兵士の位置に影響を与えません。$2$ 番目の命令では、列の $1$ 番目の兵士が準備完了で $2$ 番目の兵士が準備完了ではないため、彼らは位置を入れ替えます。$3$ 番目の命令は再び効果がありません。現在、列の $1$ 番目の兵士は準備完了ではなく、列の $4$ 番目の兵士は準備完了であるため、最後の命令の結果として彼らが入れ替わることはありません。最終的に、列の $1$ 番目の兵士だけが準備完了ではない状態になります。これは $k=3$ の場合において、バイトザールの意図通りに終了する唯一の初期配置です。

したがって、各 $k$ に対する可能性の数は数列 $[4, 0, 1, 1]$ となります。