#include <vector>
#include <cstring>
using namespace std;

const int MAXN = 105;
bool graph[MAXN][MAXN];
bool in_team[MAXN];
int n, m;
int max_size = 0;
bool best_in_team[MAXN];

void find_max_independent_set(int current, int count) {
    if (current > n) {
        if (count > max_size) {
            max_size = count;
            memcpy(best_in_team, in_team, sizeof(in_team));
        }
        return;
    }
    
    // Try to include current resident in the team if possible
    bool can_include = true;
    for (int i = 1; i < current; ++i) {
        if (in_team[i] && graph[i][current]) {
            can_include = false;
            break;
        }
    }
    
    if (can_include) {
        in_team[current] = true;
        find_max_independent_set(current + 1, count + 1);
    }
    
    // Or try not to include current resident
    in_team[current] = false;
    find_max_independent_set(current + 1, count);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> n >> m;
    
    // Initialize graph
    memset(graph, false, sizeof(graph));
    
    // Read edges
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        graph[u][v] = graph[v][u] = true;
    }
    
    // Find maximum independent set
    find_max_independent_set(1, 0);
    
    // Output the results
    cout << max_size << "\n";
    for (int i = 1; i <= n; ++i) {
        cout << best_in_team[i] << " ";
    }
    cout << "\n";
    
    return 0;
}