vertex cover

#include <bits/stdc++.h>
#define MAX 100007

using namespace std;

vector<int> graph[MAX], is_leaf;
int vis[MAX], parent[MAX], ans[MAX], n, m;

int dfs(int no){
    int leaf = true;
    //cout << no << endl;
    int cont = 0;
    for(int i = 0; i < graph[no].size(); i++){
        int filho = graph[no][i];
        if(!vis[filho]){
            leaf = false;
            vis[filho] = true;
            cont = cont || dfs(filho);
        }
    }
    cout << no << " " << cont << endl;
    ans[no] = cont;
    if(leaf) return 1;
    return !cont;
}


int main(){
    scanf("%d %d", &n, &m);
    for(int i = 0; i < m; i++){
        int a, b; scanf("%d %d", &a, &b);
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    // cout << "-----------\n";
    // for(int i = 1; i <= n; i++){
    //     for(int j = 0; j < graph[i].size(); j++){
    //         cout << graph[i][j] << " ";
    //     }
    //     cout << endl;
    // }
    // cout << "-----------\n";
    vis[1] = true;
    dfs(1);


    for(int i = 1; i <= n; i++) cout << ans[i] << " ";
    cout << endl;
    return 0;
}