import algorithm, tables, sets, lists, queues, intsets, critbits, sequtils, strutils, math, future
type
SplayNode*[Key,T] = ref object
## Node for Splay Tree
left* : SplayNode[Key,T]
right* : SplayNode[Key,T]
parent* : SplayNode[Key,T]
key* : Key
value* : T
size* : int
SplayTree*[Key,T] = object
## Self-Balancing Binary Search Tree
root* : SplayNode[Key,T]
comp* : proc(x : Key,y : Key) : bool
proc newSplayNode[Key,T](key : Key , val : T) : SplayNode[Key,T] =
## Create new SplayNode. O(1)
var x : SplayNode[Key,T] = new SplayNode[Key,T]
x.left = nil
x.right = nil
x.parent = nil
x.key = key
x.value = val
x.size = 1
return x
proc newSplayTree*[Key,T](comp : proc(x : Key,y : Key) : bool) : SplayTree[Key,T] =
## Create new Splay Tree. O(1)
var splay : SplayTree[Key,T]
splay.root = nil
splay.comp = comp
return splay
proc size_update[Key,T](x : var SplayNode[Key,T]) =
if x != nil:
x.size = 1 + x.left.node_size() + x.right.node_size()
proc set_left[Key,T](par : var SplayNode[Key,T] , x : var SplayNode[Key,T]) =
if par != nil :
par.left = x
if x != nil :
x.parent = par
par.size_update()
proc set_right[Key,T](par : var SplayNode[Key,T] , x : var SplayNode[Key,T]) =
if par != nil :
par.right = x
if x != nil :
x.parent = par
par.size_update()
proc node_size[Key,T](x : SplayNode[Key,T]) : int =
if x == nil:
return 0
return x.size
proc zig[Key,T](x : var SplayNode[Key,T]) =
var p = x.parent
p.set_left(x.right)
if p.parent != nil:
if(p.parent.left == p):
p.parent.set_left(x)
else:
p.parent.set_right(x)
else:
x.parent = nil
x.set_right(p)
proc zag[Key,T](x : var SplayNode[Key,T]) =
var p = x.parent
p.set_right(x.left)
if p.parent != nil:
if(p.parent.left == p):
p.parent.set_left(x)
else:
p.parent.set_right(x)
else:
x.parent = nil
x.set_left(p)
proc splay*[Key,T](sp_tree : var SplayTree[Key,T],x : var SplayNode[Key,T]) =
## Splaying operation of node x. amortized O(logN)
if x == nil:
return
while x.parent != nil:
if x.parent.parent == nil:
if x.parent.left == x:
zig(x)
else:
zag(x)
elif x.parent.parent.left == x.parent and x.parent.left == x:
zig(x.parent)
zig(x)
elif x.parent.parent.left == x.parent and x.parent.right == x:
zag(x)
zig(x)
elif x.parent.parent.right == x.parent and x.parent.right == x:
zag(x.parent)
zag(x)
else:
zig(x)
zag(x)
sp_tree.root = x
proc find*[Key,T](sp_tree : var SplayTree[Key,T] , key : Key) : bool =
## if the node with the key exists, splay it and return true. else splay the last node and return false. amortized O(logN)
var z : SplayNode[Key,T] = sp_tree.root
var p : SplayNode[Key,T] = nil
while z != nil:
p = z
if sp_tree.comp(z.key,key):
z = z.right
elif sp_tree.comp(key,z.key):
z = z.left
else:
sp_tree.splay(z)
return true
sp_tree.splay(p)
return false
proc insert*[Key,T](sp_tree : var SplayTree[Key,T] , key : Key , val : T) =
## insert the node with key and val. if find the node with the key, do nothing. amortized O(logN)
if(sp_tree.find(key)):
return
var z = newSplayNode(key,val)
if sp_tree.root == nil:
sp_tree.root = z
elif sp_tree.comp(sp_tree.root.key,key):
z.set_right(sp_tree.root.right)
sp_tree.root.set_right(z)
else:
z.set_left(sp_tree.root.left)
sp_tree.root.set_left(z)
sp_tree.splay(z)
proc erase*[Key,T](sp_tree : var SplayTree[Key,T] , key : Key) : bool =
## erase the node with the key. amortized O(logN)
if not sp_tree.find(key):
return false
var z = sp_tree.root
if z.left == nil and z.right == nil:
sp_tree.root = nil
elif z.left == nil:
sp_tree.root = z.right
sp_tree.root.parent = nil
elif z.right == nil:
sp_tree.root = z.left
sp_tree.root.parent = nil
else:
var lm = z.left
while lm.right != nil:
lm = lm.right
z.left.parent = nil
sp_tree.splay(lm)
sp_tree.root = lm
sp_tree.root.set_right(z.right)
return true
proc size*[Key,T](sp_tree : SplayTree[Key,T]) : int =
## size of Splay Tree. O(1)
return sp_tree.root.node_size
proc nth_node*[Key,T](sp_tree : SplayTree[Key,T] , n : int) : ref int =
## return the nth node's key of key. if it doesn't exist, return nil. amortized O(logN)
var now = n
var z = sp_tree.root
while z != nil:
if z.left.node_size == now:
var n = new int
n[] = z.key
return n
if z.left.node_size < now:
now -= z.left.node_size + 1
z = z.right
else:
z = z.left
return nil
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 = newSplayTree[int , bool](proc(x , y : int) : bool = return x < y)
n = g.n
cmp = newSeqWith(n , -1)
dfs : proc(v , f , k : int)
k = 0
for b in bridge:
st.insert(b.a * g.n + b.b,false)
dfs = proc(v,f,k : int) =
cmp[v] = k
for e in g[v]:
if cmp[e.to] == -1 and not st.find((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"