1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <cstdio>
#include <unordered_set>

using namespace std;

int a[1000], b[1000];
size_t x[36];

unordered_set<long> s, d, t;

int main()
{
  int n, m;
  scanf("%i%i", &n, &m);
  x[0]=1;
  for (int i = 0; i<=n; i++) for (int j = i; j>0; j--) x[j]+=x[j-1];
  for (int i = 0; i<m; i++) scanf("%i%i", &a[i], &b[i]);
  for (int i = 1; i<=n; i++)
  {
    s.clear();
    for (int j = 0; j<=n-i; j++) s.insert(((1l<<i)-1l)<<j);
    for (int j = m-1; j>=0; j--)
    {
      long p = 1l<<(a[j]-1);
      long q = 1l<<(b[j]-1);
      d.clear();
      t.clear();
      for (const long &e: s)
      {
        if (!(e&p)<!(e&q)) if (!s.count((e&~p)|q)) d.insert(e);
        if (!(e&p)>!(e&q)) if (!s.count((e&~q)|p)) t.insert((e&~q)|p);
      }
      for (const long &e: d) s.erase(e);
      for (const long &e: t) s.insert(e);
      if (s.size()==x[i]) break;
    }
    printf("%li%c", s.size()%2, " \n"[i==n]);
  }
  return 0;
}