拜特城（Bajtocja）再次計畫進攻比特城（Bitocja）。拜特雷（Bajtogrom）精銳特種部隊共有 $n$ 名士兵，他們在今天早上的集合中排成一列。負責執行登陸任務的拜特扎爾（Bajtazar）將軍將他們從左到右的位置編號為 $1$ 到 $n$。

每名士兵要麼準備好執行登陸任務，要麼因為法規修訂而需要額外訓練。拜特扎爾將軍希望所有準備好登陸的士兵在隊列中形成一個連續的區間。更正式地說，他希望不存在這樣的士兵位置三元組 $1 \le i < j < k \le n$，使得第 $i$ 位和第 $k$ 位的士兵準備好登陸，而第 $j$ 位的士兵沒有準備好。

由於這個條件預設可能無法滿足，拜特扎爾將發布 $m$ 道命令。在第 $i$ 道命令中，他會命令位於位置 $a_i$ 和 $b_i$ 的士兵進行溝通以交換位置。士兵們僅在「第 $a_i$ 位的士兵準備好登陸，且第 $b_i$ 位的士兵沒有準備好」的情況下才會交換位置。

拜特扎爾已經選定了一系列命令並打算發布它們。然而，他不知道有多少士兵準備好登陸，也不知道他們分別位於哪些位置。因此，對於每個介於 $1$ 到 $n$（含）之間的整數 $k$，他想解決以下問題：考慮所有 $\binom{n}{k}$ 種初始配置（其中恰好有 $k$ 名士兵準備好登陸），在執行完所有命令後，有多少種配置滿足拜特扎爾的條件（即準備好登陸的士兵形成一個連續的區間）？請幫助他計算這些數值！

注意：由於在「演算法競賽」（Potyczki Algorytmiczne）中有許多初學者參賽，我們決定不以大數困擾你們。因此，對於每個 $k$，你只需要輸出可能性數量除以 $2$ 的餘數即可。

輸入格式

輸入的第一行包含兩個整數 $n$ 和 $m$ ($2 \le n \le 35; 1 \le m \le 1\,000$)，分別表示隊列中的士兵人數和命令數量。

接下來的 $m$ 行描述了這些命令；第 $i$ 行包含兩個整數 $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

說明

如果最初只有一名士兵準備好登陸，那麼他肯定會構成一個（單元素的）連續區間。然而，不存在兩名士兵準備好登陸且最終相鄰的情況。

考慮一種情況，除了隊列中的第二名士兵外，其餘所有士兵都準備好登陸。第一道命令不會影響士兵的位置。在第二道命令後，因為隊列中的第一名士兵準備好了，而第二名士兵沒有，他們會交換位置。第三道命令同樣不會產生效果。因為現在隊列中的第一名士兵沒有準備好登陸，而第四名士兵準備好了，所以他們不會在最後一道命令中交換位置。最終，只有隊列中的第一名士兵沒有準備好登陸。這是 $k = 3$ 時唯一符合拜特扎爾意圖的初始配置。

因此，對於後續的 $k$，可能性數量對應的數列為 $[4, 0, 1, 1]$。