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
#include <iostream>
using namespace std;

int suma(int n)
{
    int odp=0;
    while(n>0){
        odp=odp+(n%2);
        n=n/2;
    }
    return odp;
}

int rozkaz[1'007][2];
int maska[40];
int out[40];

int main()
{
    int n, m, ost, pie;
    cin>>n>>m;
    for(int a=0; a<m; a++)
        cin>>rozkaz[a][0]>>rozkaz[a][1];
    for(int a=0; a<(1<<n); a++)
    {
        for(int i=0; i<n; i++)
            maska[i]=(a/(1<<i))%2;
        for(int i=0; i<m; i++)
        {
            if(maska[rozkaz[i][0]-1]==1)
                swap(maska[rozkaz[i][0]-1],maska[rozkaz[i][1]-1]);
        }
        pie=-1;
        for(int i=0; i<n; i++)
        {
            if(maska[i]==1)
                ost=i;
            if(maska[i]==1 && pie==-1)
                pie=i;
        }
        if((ost-pie+1)==suma(a))
            out[suma(a)]++;
        out[suma(a)]=(out[suma(a)])%2;
    }
    for(int a=1; a<=n; a++)
        cout<<out[a]<<" ";
}