데산트 3

바이토차가 다시 한 번 비토차를 공격할 계획이다. 엘리트 특수부대 바이토그롬에는 $n$명의 병사가 있으며, 오늘 아침 집합에서 한 줄로 섰다. 상륙 작전을 맡은 바이타자르 장군이 왼쪽에서 오른쪽으로 위치에 $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$에 대해 다음 문제를 풀고자 한다. 준비된 병사가 정확히 $k$명인 초기 배치는 $\binom{n}{k}$가지이다. 모든 명령을 수행한 뒤에도 바이타자르의 조건이 성립하는, 즉 준비된 병사들이 연속된 구간을 이루는 배치는 몇 가지인가? 이 값들을 구하는 것을 도와라.

참고로 알고리즘 대회에는 초보자가 많이 참가하므로 큰 수는 다루지 않기로 했다. 따라서 각 $k$에 대해 가짓수를 소수 2로 나눈 나머지를 구하면 된다.

첫 줄에 두 정수 $n$과 $m$($2 \le n \le 35$; $1 \le m \le 1000$)이 주어진다. 각각 줄의 병사 수와 명령의 개수이다.

이어지는 $m$개의 줄에는 각각 두 정수 $a_i$와 $b_i$($1 \le a_i, b_i \le n$; $a_i \ne b_i$)가 주어지며, 명령의 내용은 문제에 설명한 그대로이다.

첫 줄에 공백으로 구분된 정수 $n$개를 출력한다. $k$번째 정수는 준비된 병사가 정확히 $k$명인 초기 배치 중, 모든 명령을 수행한 뒤 준비된 병사들이 연속된 구간을 이루는 배치의 개수를 2로 나눈 나머지이다.

초기에 준비된 병사가 한 명뿐이라면, 그 병사는 길이 1의 연속 구간을 반드시 이룬다. 반면 준비된 병사가 두 명인 경우에는 최종적으로 두 병사가 서로 붙어 서는 상황이 존재하지 않는다.

줄에서 두 번째 병사만 준비되지 않은 상황을 생각해 보자. 첫 번째 명령은 위치를 바꾸지 않는다. 두 번째 명령 후에는 첫 번째 병사가 준비되어 있고 두 번째 병사는 그렇지 않으므로 둘이 자리를 바꾼다. 세 번째 명령은 다시 효과가 없다. 이제 첫 번째 병사는 준비되지 않았고 네 번째 병사는 준비되어 있으므로, 마지막 명령에서는 자리를 바꾸지 않는다. 결국 준비되지 않은 병사는 첫 번째 병사뿐이다. 이는 $k = 3$에서 바이타자르의 의도대로 끝나는 유일한 초기 배치이다.

따라서 이후 $k$에 대한 가짓수는 $[4, 0, 1, 1]$이다.