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
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
#include <cstdio>

using namespace std;

int n, m, next_variable_id;
int orders[1000][2];
int result[36];
int state[36]; // 0 - not ready; 1 - ready; 2+ - pointer to variable
int variable[2000]; // number inside means number of places where it was used (0 => invalidated, no usage anymore)

int main() {
  // read
  scanf("%d %d", &n, &m);
  for (int i = 0; i < m; i++) {
    scanf("%d %d", &orders[i][0], &orders[i][1]);
  }

  // initialize global state
  result[1] = n % 2;
  result[n] = 1;
  for (int i = 2; i < n; i++) {
    result[i] = 0;
  }

  // calculate
  for (int k = 2; k < n; k++) {
    for (int start_pos = n - k + 1; start_pos > 0; start_pos--) {
      // initialize local sub-state
      next_variable_id = 2;
      for (int i = 1; i < start_pos; i++) {
        state[i] = 0;
      }
      for (int i = start_pos; i < start_pos + k; i++) {
        state[i] = 1;
      }
      for (int i = start_pos + k; i <= n; i++) {
        state[i] = 0;
      }
      bool incorrect = false;

      // iterate through orders from the end
      for (int order = m - 1; order >= 0; order--) {
        if (state[orders[order][1]] > 1) { // soldier maybe is there, maybe not (behind variable)
          if (variable[state[orders[order][1]]] == 0) { // if variable is invalidated it means that there is no soldier
            // after setting 0 here (no soldier), we will go in the condition == 0 a few lines below (20+ lines below)
            state[orders[order][1]] = 0;
          } else {
            if (state[orders[order][0]] == 0) { // on source field we don't have solidier => propagate variable there as well
              variable[state[orders[order][1]]] += 1;
              state[orders[order][0]] = state[orders[order][1]];
            } else if (state[orders[order][0]] == 1) { // on source field we have soldier => it means that on destiantion we need to have this as well

              // TODO: to invalidowanie tez jest na 99.9% do poprawy, bo myslalem, ze tylko jedno moze byc, a pod zmiennymi moze byc 2 lub wiecej zolnierzy


              variable[state[orders[order][1]]] = 0; // invalidate variable (== no soldier on all fields marked by this variable)
              state[orders[order][1]] = 1; // we have soldier on destination now
            } else { // on source field we maybe have or not soldier (variable) => replace this variable by ours


              // TODO: naprawic!!!! clash zmiennych, jeśli w docelowym jest 0, to w zrodlowym nie nmoze byc 1 (?)


              // replace variable only if it's differnt than in destination (replacing would not change anything)
              if (state[orders[order][0]] != state[orders[order][1]]) {
                // because given variable can be invalidated already (== 0), we don't want to go to -1 or lower
                if (variable[state[orders[order][0]]] > 0) {
                  variable[state[orders[order][0]]] -= 1;
                }
                variable[state[orders[order][1]]] += 1;
                state[orders[order][0]] = state[orders[order][1]];
              }
            }
          }
        }
        // DO NOT put else here, since if variable was invalidated above, it will need to go to == 0 below
        if (state[orders[order][1]] == 0) { // soldier not ready should be there
          if (state[orders[order][0]] == 1) { // on source field we should have ready solider => incorrect
            incorrect = true;
            break;
          } else if (state[orders[order][0]] > 1) { // on source field we considered to have solider => but we cannot
            // because given variable can be invalidated already (== 0), we don't want to go to -1 or lower
            if (variable[state[orders[order][0]]] > 0) {
              variable[state[orders[order][0]]] -= 1;
            }
            state[orders[order][0]] = 0;
          } // if there was no soldier on source field => that's OK, do nothing
        } else if (state[orders[order][1]] == 1) { // soldier ready should be there
          if (state[orders[order][0]] == 0) { // on source field we don't have solider => create variable - soldier here or there
            variable[next_variable_id] = 2;
            state[orders[order][0]] = next_variable_id;
            state[orders[order][1]] = next_variable_id;
            next_variable_id++;
          } else if (state[orders[order][0]] > 1) { // on source field maybe we have soldier (or maybe not) => we have new variable and take over this source


            // TODO: NAPRAWIC!!!!
            // TODO: NIE nowa zmienna, a spropagowanie do docelowej tej samej zmiennej, co w source - i musimy trzymac dwa liczniki (liczba wystapien, liczba zolnierzy)
            // TODO: a potem na koniec musimy liczyc kombinacje!!! (n nad k => liczba wystapien zmiennych nad liczba zolnierzy) => czy jest parzysta czy nie
            // TODO: tablica stalych??? policzyc raz na poczatku? a moze da sie latwo stwierdzic?



            // because given variable can be invalidated already (== 0), we don't want to go to -1 or lower
            if (variable[state[orders[order][0]]] > 0) {
              variable[state[orders[order][0]]] -= 1;
            }
            variable[next_variable_id] = 2;
            state[orders[order][0]] = next_variable_id;
            state[orders[order][1]] = next_variable_id;
            next_variable_id++;
          } // if there was soldier on source field => that's OK, do nothing
        }
      }

      // after going through all orders, if state is correct, add result to our array of results
      if (!incorrect) {
        bool is_even = false;
        // we need to check if we have any variable for which number of occurrences is even (if it's even, then we add +0, otherwise +1)
        for (int i = 2; i < next_variable_id; i++) {
          if ((variable[i] > 0) && (variable[i] % 2 == 0)) {
            is_even = true;
            break;
          }
        }
        // add +1 if NOT even
        if (!is_even) {
          result[k] = (result[k] + 1) % 2;
        }
      }
    }
  }

  // print
  printf("%d", result[1]);
  for (int i = 2; i <= n; i++) {
    printf(" %d", result[i]);
  }
  printf("\n");

  return 0;
}