ARC039 D問題 旅行会社高橋君

考え方は簡単。というより一瞬で気づいた。
ただ、この問題、二重辺連結成分分解、まぁつまり橋の検出と、LowestCommonAncesterの実装をしないといけないのでライブラリとか持ってないと地獄…つらかった…。
まず、a,b,cという始点,中継点,終点が与えられたときa,b またはb,cが同じ二重辺連結成分に入っていればどう考えてもおｋ
入っていないときは、二重辺連結成分分解でただの木にしたあと、a,cの間にbが存在すればよいということになる。つまり、aからbの距離とbからcの距離の和がaからcの距離の和になっていればいいのである。これをするにはLCAを使うのじゃ〜〜
二重辺連結成分分解はlowlink理解してれば簡単。LCAもまぁそこまで難しい話じゃないので、理解してスパゲッティコードと蟻本からとってきた。

struct Edge {
    int src, dst;
    Edge(int src, int dst) : src(src), dst(dst) {}
};

typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

void visit(const Graph & g, int v, int u,
        Edges& brdg, vector< vector<int> >& tecomp,
        stack<int>& roots, stack<int>& S, vector<bool>& inS,
        vector<int>& num, int& time) {
    num[v] = ++time;
    S.push(v); inS[v] = true;
    roots.push(v);
    for (auto e : g[v]) {
        int w = e.dst;
        if (num[w] == 0) //non-used
            visit(g, w, v, brdg, tecomp, roots, S, inS, num, time);
        else if (u != w && inS[w])
            while (num[roots.top()] > num[w]) roots.pop();
    }
    if (v == roots.top()) {
        brdg.push_back(Edge(u, v));
        tecomp.push_back(vector<int>());
        while (true) {
            int w = S.top(); S.pop(); inS[w] = false;
            tecomp.back().push_back(w);
            if (v == w) break;
        }
        roots.pop();
    }
}

void bridge(const Graph& g, Edges& brdg, vector< vector<int> >& tecomp) {
    const int n = (int)g.size();
    vector<int> num(n);
    vector<bool> inS(n);
    stack<int> roots, S;
    int time = 0;
    for (int u = 0; u < n; u++) if (num[u] == 0) {
        visit(g, u, n, brdg, tecomp, roots, S, inS, num, time);
        brdg.pop_back();
    }
}

template<int V>
struct LowestCommonAncestor {
    const static int LG = 25; //頂点の数のlogだけどVが2^25を超えることないしこれでよさ気
    int ro[LG][V]; //ro[i][j]で、頂点jの2^i親にあたる頂点を指す
    int dps[V]; //根からの深さ
    vector<int> g[V];
    /// i-jに有向辺を張る
    void add(int i, int j) {
        g[i].push_back(j);
        g[j].push_back(i);
    }
    //initで呼ばれるので無視して
    void dfs(int p, int b) {
        assert(ro[0][p] == -1);
        ro[0][p] = b;
        dps[p] = (b == -1) ? 0 : dps[b]+1;
        for (int d: g[p]) {
            if (d == b) continue;
            dfs(d, p);
        }
    }
    /// 事前処理を行う rはroot頂点のid
    void init(int r) {
        memset(ro, -1, sizeof(ro));
        dfs(r, -1);
        for (int i = 0; i < LG-1; i++) {
            for (int j = 0; j < V; j++) {
                ro[i+1][j] = (ro[i][j] == -1) ? -1 : ro[i][ro[i][j]];
            }
        }
    }
    /// lとrの頂点のLCAを求める
    int query(int l, int r) const {
        if (dps[l] < dps[r]) swap(l, r);
        int dd = dps[l]-dps[r];
        for (int i = LG-1; i >= 0; i--) {
            if (dd < (1<<i)) continue;
            dd -= 1<<i;
            l = ro[i][l];
        }
        if (l == r) return l;
        for (int i = LG-1; i >= 0; i--) {
            if (ro[i][l] == ro[i][r]) continue;
            l = ro[i][l]; r = ro[i][r];
        }
        return ro[0][l];
    }
    int dist(int u, int v) const {
        int p = query(u, v);
        return (dps[u]-dps[p]) + (dps[v]-dps[p]);
    }
};

const int MAXN = 100010;
int A[MAXN];
LowestCommonAncestor<MAXN> LCA;

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    int N,M;
    cin >> N >> M;
    Graph g(N);
    for(int i=0; i<M; i++){
        int x, y;
        cin >> x >> y;
        x--; y--;
        g[x].push_back(Edge(x, y));
        g[y].push_back(Edge(y, x));
    }
    Edges brdg;
    vector< vector<int> > tecomp;
    bridge(g, brdg, tecomp);
    for(int i=0; i<len(tecomp); i++){
        for(auto el : tecomp[i]){
            A[el] = i;
        }
    }
    for(int i=0; i<len(brdg); i++){
        LCA.add(A[brdg[i].src], A[brdg[i].dst]);
    }
    LCA.init(0);
    int Q; cin >> Q;
    for(int i=0; i<Q; i++){
        int a, b, c;
        cin >> a >> b >> c;
        a--; b--; c--;
        if(A[a] == A[b] || A[b] == A[c]){
            cout << "OK" << endl;
            continue;
        }
        if(LCA.dist(A[a], A[b]) + LCA.dist(A[b], A[c]) == LCA.dist(A[a], A[c])){
            cout << "OK" << endl;
            continue;
        }
        cout << "NG" << endl;
    }
}