#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;
    }
};

I2luY2x1ZGUgPGxpc3Q+CiNpbmNsdWRlIDx2ZWN0b3I+CgpjbGFzcyBHcmFwaCB7CiAgICBpbnQgdmVydGV4X2NvdW50OwogICAgc3RkOjpsaXN0PGludD4gKmFkajsKcHVibGljOgogICAgR3JhcGgoaW50IHZlcnRleF9jb3VudCkgewogICAgICAgIHRoaXMtPnZlcnRleF9jb3VudCA9IHZlcnRleF9jb3VudDsKICAgICAgICBhZGogPSBuZXcgc3RkOjpsaXN0PGludD5bdmVydGV4X2NvdW50XTsKICAgIH0KICAgIHZvaWQgYWRkRWRnZShpbnQgdiwgaW50IHcpIHsKICAgICAgICBhZGpbdl0ucHVzaF9iYWNrKHcpOwogICAgICAgIGFkalt3XS5wdXNoX2JhY2sodik7CiAgICB9CiAgICBzdGQ6OnZlY3Rvcjxib29sPiBnZXRfdmVydGV4X2NvdmVyKCkgewogICAgICAgIHN0ZDo6dmVjdG9yPGJvb2w+IHZpc2l0ZWQodmVydGV4X2NvdW50LCBmYWxzZSk7CiAgICAgICAgZm9yIChpbnQgdSA9IDA7IHUgPCB2ZXJ0ZXhfY291bnQ7IHUrKykgewogICAgICAgICAgICBpZiAodmlzaXRlZFt1XSkgY29udGludWU7CiAgICAgICAgICAgIGZvciAoaW50IHYgOiBhZGpbdV0pIHsKICAgICAgICAgICAgICAgIGlmICh2aXNpdGVkW3ZdKSBjb250aW51ZTsKICAgICAgICAgICAgICAgIHZpc2l0ZWRbdl0gPSB2aXNpdGVkW3VdID0gdHJ1ZTsKICAgICAgICAgICAgICAgIGJyZWFrOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgICAgIHJldHVybiB2aXNpdGVkOwogICAgfQp9Ow==