#include <iostream>
#include <vector>

typedef int                             Node;
typedef std::vector<std::vector<Node>>  List;

void dfs(List& neighbours, std::vector<bool>& visited, Node u)
{
    visited[u] = true;

    for (Node v : neighbours[u]) {
        if (!visited[v]) { 
            dfs(neighbours, visited, v);
        }
    }
}

List transpose(List& neighbours)
{
    List neighbours_T(neighbours.size());

    for (Node u = 0; u < neighbours.size(); u++) {
        for (Node v : neighbours[u]) {
            neighbours_T[v].push_back(u);
        }
    }

    return neighbours_T;
}

bool scc(List& neighbours)
{
    std::vector<bool> visited(neighbours.size(), false);
    dfs(neighbours, visited, 0);
    for (Node u = 0; u < neighbours.size(); u++) {
        if (!visited[u]) {
            return false;
        }
        visited[u] = false;
    }

    List neighbours_T = transpose(neighbours);

    dfs(neighbours_T, visited, 0);
    for (Node u = 0; u < neighbours.size(); u++) {
        if (!visited[u]) {
            return false;
        }
    }

    return true;
}

bool is_euler(List& neighbours) 
{
    // Proveri da li je komponenta jake povezanosti?
    if (!scc(neighbours)) {
        return false;
    }

    // Proveri da li su svi cvorovi parnog stepena?
    std::vector<int> degree(neighbours.size(), 0);
    for (Node u = 0; u < neighbours.size(); u++) {
        if (neighbours[u].size() % 2 != 0) {
            return false;
        }
    }

    return true;
}

int main(void)
{
    List neighbours = {
        {4, 4},
        {2, 3, 5, 5},
        {1, 5},
        {1, 5},
        {0, 0},
        {1, 1, 2, 3}
    };
    
    if (is_euler(neighbours)) {
        std::cout << "Jeste Ojlerov" << std::endl;
    } else {
        std::cout << "Nije Ojlerov" << std::endl;
    }

    return 0;
}