ARC039D

arc039_d.cpp

#include <algorithm>
#include <utility>
#include <vector>

using Graph = std::vector<std::vector<int>>;
using Edge = std::pair<int, int>;

class BridgeHelper {
  const Graph& graph;
  std::vector<int> ord, low;
  int k = 0;

public:
  std::vector<Edge> bridges;

  BridgeHelper(const Graph& graph) : graph(graph), ord(graph.size(), -1), low(graph.size()) {
    for (int u = 0; u < graph.size(); ++u) {
      if (ord[u] >= 0) continue;
      dfs(u);
    }
  }
  bool is_bridge(int u, int v) const {
    if (ord[u] > ord[v]) std::swap(u, v);
    return ord[u] < low[v];
  }

private:
  void dfs(int u, int p = -1) {
    ord[u] = low[u] = k;
    ++k;
    for (int v : graph[u]) {
      if (v == p) continue;
      if (ord[v] >= 0) {
        low[u] = std::min(low[u], ord[v]);
      } else {
        dfs(v, u);
        low[u] = std::min(low[u], low[v]);
      }
      if (is_bridge(u, v)) bridges.emplace_back(u, v);
    }
  }
};

struct BECC {
  std::vector<std::vector<int>> comps;
  std::vector<int> belongs;
  const BridgeHelper bridge_helper;

private:
  const Graph& graph;

public:
  BECC(const Graph& graph) : graph(graph), bridge_helper(graph), belongs(graph.size(), -1) {
    for (const auto& bridge : bridge_helper.bridges) {
      add_component(bridge.first);
      add_component(bridge.second);
    }
    add_component(0);
  }
  Graph to_tree() const {
    Graph tree(comps.size());
    for (const auto& bridge : bridge_helper.bridges) {
      int u = belongs[bridge.first], v = belongs[bridge.second];
      tree[u].emplace_back(v);
      tree[v].emplace_back(u);
    }
    return tree;
  }

private:
  void fill_component(int c, int u) {
    comps[c].emplace_back(u);
    belongs[u] = c;
    for (int v : graph[u]) {
      if (belongs[v] >= 0) continue;
      if (bridge_helper.is_bridge(u, v)) continue;
      fill_component(c, v);
    }
  }
  void add_component(int u) {
    if (belongs[u] >= 0) return;
    comps.emplace_back();
    fill_component(comps.size() - 1, u);
  }
};

struct LCA {
private:
  const Graph& tree;
  const int root;
  std::vector<int> depth;
  std::vector<std::vector<int>> parent;

public:
  LCA(const Graph& tree, int root)
      : tree(tree), root(root), depth(tree.size()),
        parent(std::__lg(tree.size()) + 1, std::vector<int>(tree.size())) {
    build(root);
    for (int k = 0; k + 1 < parent.size(); ++k) {
      for (int u = 0; u < tree.size(); ++u) {
        if (parent[k][u] < 0) {
          parent[k + 1][u] = -1;
        } else {
          parent[k + 1][u] = parent[k][parent[k][u]];
        }
      }
    }
  }
  int query(int u, int v) const {
    if (depth[u] > depth[v]) std::swap(u, v);
    for (int k = 0; k < parent.size(); ++k) {
      if ((depth[v] - depth[u]) >> k & 1) v = parent[k][v];
    }
    if (u == v) return u;
    for (int k = parent.size() - 1; k >= 0; --k) {
      if (parent[k][u] == parent[k][v]) continue;
      u = parent[k][u];
      v = parent[k][v];
    }
    return parent[0][u];
  }
  int dist(int u, int v) const { return depth[u] + depth[v] - 2 * depth[query(u, v)]; }

private:
  void build(int u, int p = -1, int d = 0) {
    parent[0][u] = p;
    depth[u] = d;
    for (int v : tree[u]) {
      if (v == p) continue;
      build(v, u, d + 1);
    }
  }
};

#include <bits/stdc++.h>

using namespace std;

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)

inline int in() {
  int x;
  scanf("%d", &x);
  return x;
}

int main() {
  int N = in(), M = in();
  Graph G(N);
  rep(i, M) {
    int u = in() - 1, v = in() - 1;
    G[u].emplace_back(v);
    G[v].emplace_back(u);
  }
  BECC becc(G);
  Graph tree = becc.to_tree();
  LCA lca(tree, 0);
  int Q = in();
  rep(i, Q) {
    int A = in() - 1, B = in() - 1, C = in() - 1;
    int X = becc.belongs[A], Y = becc.belongs[B], Z = becc.belongs[C];
    if (lca.dist(X, Z) == lca.dist(X, Y) + lca.dist(Y, Z)) {
      puts("OK");
    } else {
      puts("NG");
    }
  }
  return 0;
}