General Iroh and Commandant Bumi are heading to the Republic City to stop a rebellion. But it's quite a long travel, so in the meantime they have started discussing about possible attacking plans. Right now, they're arguing about best ways for moving soldiers during the battle. Tired of not getting a final and concise strategy, Iroh proposed a particularly original idea.

Iroh:

Bumi, look at this map: here we have all possible locations in the battle field soldiers can occupy. I know a game which can give us some ideas.

Bumi:

A game? How will a game help us here?

Iroh:

It's pretty simple, we know which location is connected to each one, and also, that all those paths between locations are one-way (it's too dangerous to have two ways paths), so we place some soldiers at random initial locations, take turns, and in each turn, we try to make a valid move with one soldier from one location to another. Eventually, we won't be able to move any man so, the first one which is not able to perform any valid move, loses. One important thing is, at some moment, we may have some men at the same field location.

Bumi:

Are you sure we are gonna end this? We have so many locations and paths... don't know, soldiers could be moving in circles for ever.

Iroh:

Take it easy man, those paths were built by the best architects I've ever known, so there is no way that could happen.

Bumi:

Well, I still don't get how does this help us.

Iroh:

Me neither, but greatest generals from the Earth Kingdom created their strategies from this game, so, who knows?

Bumi:

Ok, I'm in. Who plays first?

Iroh:

You go first my friend. Just make sure you always do your best, because I will show no mercy to you :).

Input Format

First line in the input contains two integers N and M, describing the number of locations and paths between them, respectively. M lines follow, each one with two integers u and v, denoting a one-way path from u to v. 

Then comes a line with a single integer Q, denoting how many times Bumi and Iroh played the game over the given field. Q queries follow each one with two lines, first one with a single integer K, the number of soldiers in the field; and second one with K integers b_i separated by space, each one denoting the initial location of some soldier.

Constraints

$1 < N <= 10^{5} $

$1 <= M <= 10^{6} $

1 <= u, v, b_i <= N 

$1 <= K <= 10^{2} $

$1 <= Q <= 10^{5}  $

Output Format

Output Q lines, each one saying Bumi if Bumi should be the winner of the corresponding game or Iroh otherwise. 

Remember that, being both top strategy masters, they will always perform the best possible move each turn.

Sample Input
10 10
1 10
3 10
7 8
6 8
7 4
9 4
7 6
5 8
1 8
2 8
5
4
10 7 6 4
3
1 9 4
3
8 3 5
3
4 9 7
3
7 9 10

Sample Output
Bumi
Iroh
Iroh
Bumi
Bumi

Source: hackerrank | Difficulty: MEDIUM
Tags: Game theory


Solutions:
from functools import reduce
from operator import xor
from itertools import count
from sys import stderr

def main():
	(nvert, nedges) = readints()
	children = [[] for _ in range(nvert + 1)]
	parents = [[] for _ in range(nvert + 1)]
	for edge in range(nedges):
		(start, stop) = readints()
		children[start].append(stop)
		parents[stop].append(start)
	nim = getnim(parents, children)
	(ngames,) = readints()
	for _ in range(ngames):
		(npieces,) = readints()
		pieces = readints()
		assert npieces == len(pieces)
		score = reduce(xor, (nim[piece] for piece in pieces))
		print('Bumi' if score != 0 else 'Iroh')

def getnim(parents, children):
	nim = [None] * len(parents)
	unknown = [len(c) for c in children]
	stack = [vert for (vert, u) in enumerate(unknown) if u == 0]
	while stack:
		vert = stack.pop()
		cset = set((nim[child] for child in children[vert]))
		for i in count():
			if i not in cset:
				nim[vert] = i
				break
		for parent in parents[vert]:
			unknown[parent] -= 1
			if unknown[parent] == 0:
				stack.append(parent)
	return nim

def readints():
	return [int(f) for f in input().split()]
main()


(N, M) = map(int, input().split())
G = {n: [] for n in range(1, N + 1)}
cnt = [0] * (N + 1)
sg = {n: -1 for n in range(1, N + 1)}
for _ in range(M):
	(u, v) = map(int, input().split())
	G[u].append(v)
	cnt[v] += 1

def dfs(v, G, sg):
	sz = len(G[v])
	if sz == 0:
		sg[v] = 0
		return
	elif sg[v] != -1:
		return
	for child in G[v]:
		dfs(child, G, sg)
	s = {sg[child] for child in G[v]}
	g = 0
	while g in s:
		g += 1
	sg[v] = g
for v in range(1, N + 1):
	if cnt[v] == 0:
		dfs(v, G, sg)
from functools import reduce
import operator
Q = int(input())
for q in range(Q):
	_ = int(input())
	locs = list(map(int, input().split()))
	res = reduce(operator.xor, (sg[loc] for loc in locs))
	print('Bumi' if res else 'Iroh')


(n, m) = map(int, input().split())
a = [[] for i in range(n + 1)]
g = [-1 for i in range(n + 1)]

def mex(b):
	for i in range(100000):
		if i not in b:
			return i

def findg(x):
	if g[x] != -1:
		return g[x]
	g[x] = mex([findg(i) for i in a[x]])
	return g[x]
for i in range(m):
	(x, y) = map(int, input().split())
	a[x].append(y)
for i in range(1, n + 1):
	if a[i] is None:
		g[i] = 0
for i in range(1, n + 1):
	g[i] = findg(i)
for i in range(int(input())):
	s = int(input())
	b = list(map(int, input().split()))
	ans = 0
	for j in b:
		ans = ans ^ g[j]
	if ans == 0:
		print('Iroh')
	else:
		print('Bumi')


from collections import defaultdict
graph = defaultdict(list)

def mex(S):
	i = 0
	while i in S:
		i += 1
	return i

def SG(u, cache={}):
	if u in cache:
		return cache[u]
	S = set()
	for v in graph[u]:
		S.add(SG(v))
	cache[u] = mex(S)
	return cache[u]
(N, M) = map(int, input().split())
for i in range(M):
	(u, v) = map(int, input().split())
	graph[u].append(v)
Q = int(input())
for i in range(Q):
	K = int(input())
	b = list(map(int, input().split()))
	nim_sum = 0
	for b_i in b:
		nim_sum ^= SG(b_i)
	print(['Iroh', 'Bumi'][nim_sum > 0])


from functools import reduce

def mex(s):
	i = 0
	while i in s:
		i += 1
	return i

def calc_gnum(x):
	if gnum[x] != -1:
		return gnum[x]
	if not graph[x]:
		gnum[x] = 0
		return gnum[x]
	gnum[x] = mex({calc_gnum(i) for i in graph[x]})
	return gnum[x]
(n, m) = (int(i) for i in input().split())
graph = [[] for i in range(n + 1)]
gnum = [-1] * (n + 1)
for _ in range(m):
	(i, j) = (int(i) for i in input().split())
	graph[i].append(j)
q = int(input())
for _ in range(q):
	k = int(input())
	l = [calc_gnum(int(i)) for i in input().split()]
	ans = reduce(lambda x, y: x ^ y, l)
	if ans == 0:
		print('Iroh')
	else:
		print('Bumi')


from collections import defaultdict
from functools import reduce
from operator import xor
(n, m) = map(int, input().split())

def mex(s):
	return next((i for i in range(n) if i not in s))
childs = defaultdict(set)
parents = defaultdict(set)
leaves = set(range(1, n + 1))
childnum = [0] * (n + 1)
for _ in range(m):
	(u, v) = map(int, input().split())
	leaves.discard(u)
	childs[u].add(v)
	childnum[u] += 1
	parents[v].add(u)
gnum = [0] * (n + 1)
while leaves:
	curr = leaves.pop()
	gnum[curr] = mex(set(map(gnum.__getitem__, childs[curr])))
	for p in parents[curr]:
		if childnum[p] == 1:
			leaves.add(p)
		else:
			childnum[p] -= 1
res = []
for _ in range(int(input())):
	input()
	res.append('Bumi' if reduce(xor, map(gnum.__getitem__, map(int, input().split())), 0) else 'Iroh')
print('\n'.join(res))


from functools import reduce
from operator import xor
from itertools import count
from sys import stderr

def main():
	(nvert, nedges) = readints()
	children = [[] for _ in range(nvert + 1)]
	parents = [[] for _ in range(nvert + 1)]
	for edge in range(nedges):
		(start, stop) = readints()
		children[start].append(stop)
		parents[stop].append(start)
	nim = getnim(parents, children)
	(ngames,) = readints()
	for _ in range(ngames):
		(npieces,) = readints()
		pieces = readints()
		assert npieces == len(pieces)
		score = reduce(xor, (nim[piece] for piece in pieces))
		print('Bumi' if score != 0 else 'Iroh')

def getnim(parents, children):
	nim = [None] * len(parents)
	unknown = [len(c) for c in children]
	stack = [vert for (vert, u) in enumerate(unknown) if u == 0]
	while stack:
		vert = stack.pop()
		cset = set((nim[child] for child in children[vert]))
		for i in count():
			if i not in cset:
				nim[vert] = i
				break
		for parent in parents[vert]:
			unknown[parent] -= 1
			if unknown[parent] == 0:
				stack.append(parent)
	return nim

def readints():
	return [int(f) for f in input().split()]
main()


from functools import reduce
from operator import xor
from itertools import count
from sys import stderr

def main():
	(nvert, nedges) = readints()
	children = [[] for _ in range(nvert + 1)]
	parents = [[] for _ in range(nvert + 1)]
	for edge in range(nedges):
		(start, stop) = readints()
		children[start].append(stop)
		parents[stop].append(start)
	nim = getnim(parents, children)
	(ngames,) = readints()
	for _ in range(ngames):
		(npieces,) = readints()
		pieces = readints()
		assert npieces == len(pieces)
		score = reduce(xor, (nim[piece] for piece in pieces))
		print('Bumi' if score != 0 else 'Iroh')

def getnim(parents, children):
	nim = [None] * len(parents)
	unknown = [len(c) for c in children]
	stack = [vert for (vert, u) in enumerate(unknown) if u == 0]
	while stack:
		vert = stack.pop()
		cset = set((nim[child] for child in children[vert]))
		for i in count():
			if i not in cset:
				nim[vert] = i
				break
		for parent in parents[vert]:
			unknown[parent] -= 1
			if unknown[parent] == 0:
				stack.append(parent)
	return nim

def readints():
	return [int(f) for f in input().split()]
main()