#include <list>
#include <vector>

class Graph {
    int vertex_count;
    std::list<int> *adj;
public:
    Graph(int vertex_count) {
        this->vertex_count = vertex_count;
        adj = new std::list<int>[vertex_count];
    }
    void addEdge(int v, int w) {
        adj[v].push_back(w);
        adj[w].push_back(v);
    }
    std::vector<bool> get_vertex_cover() {
        std::vector<bool> visited(vertex_count, false);
        for (int u = 0; u < vertex_count; u++) {
            if (visited[u]) continue;
            for (int v : adj[u]) {
                if (visited[v]) continue;
                visited[v] = visited[u] = true;
                break;
            }
        }
        return visited;
    }
};