import algorithm, tables, sets, lists, queues, intsets, critbits, sequtils, strutils, math, future
var input : seq[string] = @[]
var in_cnt = 0
proc gs() : string =
if input.len == in_cnt:
in_cnt = 0
input = stdin.readline.split
in_cnt += 1
return input[in_cnt - 1]
proc gi() : int =
return gs().parseInt
proc gf() : float =
return gs().parseFloat
import sequtils,sets,math
type
Edge* = object
to : int
Graph*[E] = object
edges : seq[seq[Edge]]
n : int
proc newGraph*[E](n : int) : Graph[E] =
var g : Graph[E]
g.edges = newSeqWith(n , newSeq[E](0))
g.n = n
return g
proc `[]`*[E](g : var Graph[E] , k : int) : var seq[Edge] =
return g.edges[k]
proc `[]`*[E](g : Graph[E] , k : int) : seq[Edge] =
return g.edges[k]
proc lowlink*[E](g : Graph[E]) : seq[tuple[a : int , b : int]] =
var
bridge : seq[tuple[a : int , b : int]] = @[]
n = g.n
used = newSeqWith(n , false)
ord = newSeqWith(n , 0)
low = newSeqWith(n , 0)
dfs : proc(v , K , f : int) : int
dfs = proc(v , K , f : int) : int =
var k = K
used[v] = true
ord[v] = k
low[v] = ord[v]
inc(k)
for e in g[v]:
if not used[e.to]:
k = dfs(e.to , k , v)
low[v] = min(low[v] , low[e.to])
if ord[v] < low[e.to]: bridge.add((min(v , e.to) , max(v , e.to)))
elif e.to != f: low[v] = min(low[v] , ord[e.to])
return k
discard dfs(0,0,-1)
return bridge
proc twoEdgeConnectedComponent*[E](g : Graph[E]) : tuple[cmp : seq[int] , tree : Graph[E]] =
var
bridge = g.lowlink
st = initIntSet()
n = g.n
cmp = newSeqWith(n , -1)
dfs : proc(v , f , k : int)
k = 0
for b in bridge: st.incl(b.a * g.n + b.b)
dfs = proc(v,f,k : int) =
cmp[v] = k
for e in g[v]:
if cmp[e.to] == -1 and not st.contains(min(v,e.to) * g.n + max(v,e.to)):
dfs(e.to , v , k)
for i in 0..<n:
if cmp[i] == -1:
dfs(i , -1 , k)
inc(k)
var tree = newGraph[Edge](k)
for e in bridge:
tree[cmp[e.a]].add(Edge(to : cmp[e.b]))
tree[cmp[e.b]].add(Edge(to : cmp[e.a]))
return (cmp , tree)
type LowestCommonAncestor = object
n : int
log2_n : int
parent : seq[seq[int]]
depth : seq[int]
proc initLowestCommonAncestor*[E](g : Graph[E]) : LowestCommonAncestor =
var lca : LowestCommonAncestor
lca.n = g.n
lca.log2_n = ((int)log2((float)lca.n) + 2)
lca.parent = newSeqWith(lca.log2_n , newSeqWith(lca.n,0))
lca.depth = newSeqWith(lca.n , 0)
var dfs : proc(v , f , d : int)
dfs = proc(v,f,d : int) =
lca.parent[0][v] = f
lca.depth[v] = d
for e in g[v]:
if e.to != f: dfs(e.to , v , d + 1)
dfs(0,-1,0)
for k in 0..<lca.log2_n-1:
for v in 0..<lca.n:
if lca.parent[k][v] < 0: lca.parent[k + 1][v] = -1
else: lca.parent[k + 1][v] = lca.parent[k][lca.parent[k][v]]
return lca
proc getLowestCommonAncestor*(lca : LowestCommonAncestor,a : int , b : int) : tuple[parent : int , depth : int]=
var
u = a
v = b
if lca.depth[u] > lca.depth[v]: swap(u,v)
for k in 0..<lca.log2_n:
if (((lca.depth[v] - lca.depth[u]) shr k) and 1) == 1:
v = lca.parent[k][v]
if u == v: return (u , lca.depth[u])
for k in countdown(lca.log2_n - 1 , 0):
if lca.parent[k][u] != lca.parent[k][v]:
u = lca.parent[k][u]
v = lca.parent[k][v]
u = lca.parent[0][u]
return (u , lca.depth[u])
proc dist*(lca : LowestCommonAncestor , a : int , b : int) : int =
return lca.depth[a] + lca.depth[b] - lca.getLowestCommonAncestor(a , b).depth * 2
var N = gi()
var M = gi()
var G = newGraph[Edge](N)
for i in 1..M:
var
a = gi()
b = gi()
dec(a)
dec(b)
G[a].add(Edge(to : b))
G[b].add(Edge(to : a))
var p = G.twoEdgeConnectedComponent
var lca = p.tree.initLowestCommonAncestor
var cmp = p.cmp
var Q = gi()
for i in 1..Q:
var
a = gi()
b = gi()
c = gi()
a = cmp[a - 1]
b = cmp[b - 1]
c = cmp[c - 1]
if lca.dist(a,b) + lca.dist(b,c) == lca.dist(a , c): echo "OK"
else: echo "NG"