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
#include <bits/stdc++.h>

using namespace std;

long long length, amountOfCommands;

pair<int, int> commands[1007];

long long answers[37];

unordered_set<bitset<35>> analyzed[1007];

long long count(bitset<35> values, int step)
{
    // cout << step << '\n';
    // for (int i = 0; i < length; ++i)
    // {
    //     cout << values[i];
    // }
    // cout << '\n';
    if (analyzed[step].count(values) != 0) return 0;
    analyzed[step].insert(values);
    if (step == 0)
    {
        // cout << step << '\n';
        // for (int i = 0; i < length; ++i)
        // {
        //     cout << values[i];
        // }
        // cout << '\n';
        return 1;
    }
    int a = commands[step].first;
    int b = commands[step].second;

    if (values[a] == 0 && values[b] == 0)
    {
        return count(values, step - 1);
    }
    else if (values[a] == 1 && values[b] == 1)
    {
        return count(values, step - 1);
    }
    else if (values[a] == 1 && values[b] == 0)
    {
        return 0;
    }
    else
    {
        long long sum = 0;
        sum += count(values, step - 1);
        values[a] = 1;
        values[b] = 0;
        sum += count(values, step - 1);
        return sum;
    }

    return 0;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> length >> amountOfCommands;

    for (int i = 1; i <= amountOfCommands; ++i)
    {
        int a, b;
        cin >> a >> b;
        --a; --b;
        commands[i] = make_pair(a, b);
    }

    for (int n = 1; n <= length; ++n)
    {
        for (int start = 0; start <= length - n; ++start)
        {
            bitset<35> values;
            for (int i = 0; i < length; ++i)
            {
                if (i < start || i >= start + n) values[i] = 0;
                else values[i] = 1;
            }
            long long amount = count(values, amountOfCommands);
            answers[n] += amount;
            // cout << amount << '\n';
            // if (amount > 0)
            // {
            //     for (int i = 0; i < length; ++i)
            //     {
            //         cout << values[i];
            //     }
            //     cout << '\n';
            // }
        }
        for (int i = 0; i <= amountOfCommands; ++i)
        {
            analyzed[i].clear();
        }
    }
    for (int i = 1; i <= length; ++i)
    {
        cout << (answers[i] % 2) << ' ';
    }
    cout << '\n';
}