// Directed Graph
vector<int> eulerianPath(vector<int> G[], int N) { // [x->y->...->z]  visits each edge once.
    int cnt = 0, x = 0, diff = 0;
    vector<int> in(N), ret;
    for (int v=0; v<N; v++) {
        cnt += G[v].size();
        for (int i=0; i<(int)G[v].size(); i++) in[G[v][i]]++;
    }
    for (int i=0; i<N; i++) {
        diff += abs(in[i] - (int)G[i].size());
        if (diff > 2) return vector<int>(); // unbalanced degree vertices
        if (in[i] < (int)G[i].size()) x = i; // choosing start
    }
    vector<int> S;
    S.push_back(x);
    while (!S.empty()) {
    int v = S.back();
    if (G[v].size()) {
        S.push_back(G[v].back());
        G[v].pop_back();
    } else {
        S.pop_back();
        ret.push_back(v);
    }
    }
    if ((int)ret.size() != cnt+1) return vector<int>(); // not connected
    reverse(ret.begin(), ret.end());
    return ret;
}