Read problems statements in Mandarin Chinese, Russian and Vietnamese as well. 

Kekocity's population consist of N gnomes numbered with unique ids from 1 to N. As they are very joyful gnomes, they usually send jokes to their friends right after they get any (even if they knew it before) via their social network named as Mybeard. Mybeard became popular in the city because of message auto-deletion. It takes exactly one minute to read and resend joke to mates.

Mayor of Kekocity, Mr. Shaikhinidin, is interested in understanding how the jokes are spread. He gives you database of Mybeard social network, and wants you to answer some queries on it.

You will be given a list of friends for every gnome and M queries of the following type: Who will receive a message with joke after exactly K minutes, if the creator of joke was gnome with id x?

------ Input ------ 

The first line contains a single integer N denoting the number of gnomes.
The next N lines contain the the matrix g[N][N]. Each of the i-th line, will contain N space separated integers - j-th of those will denote g[i][j]. If gnome j is friend of gnome i, then g[i][j] is 1. Otherwise it will be zero. Plese note that the friendship relationship is not bidirectional, i.e. it might happen that g[i][j] may not be equal to g[j][i]. Also one can be friend of itself also, i.e. g[i][i] may be equal to 1.
The next line contains a single integer M denoting the number of queries. The next M lines contain two integers k and x described above.

------ Output ------ 

For each query, output two lines.
In the first line, output how many gnomes will know the joke after k minutes.
In the second line, print these ids (numbering) of these gnomes in increasing order. If no one will know the joke after K minutes, then print -1 in this line.

------ Constraints ------ 

$1 ≤ N ≤ 500$
$1 ≤ M ≤ 500$
$0 ≤ k ≤ 10^{9}$
$1 ≤ x ≤ N$
$0 ≤ g[i][j] ≤ 1$

------  Subtasks  ------ 

Subtask #1 : (10 points) 

$1 ≤ N ≤ 50$
$1 ≤ M ≤ 50$
$0 ≤ k ≤ 50$
 
Subtask #2 : (15 points) 

$Original constraints$
$Every gnome has exactly one friend (for every i there is exactly one j such that g[i][j] = 1. Note that j can be equal to i) $
 
Subtask #3 : (30 points) 

$1 ≤ N ≤ 75$
$1 ≤ M ≤ 75$
$0 ≤ k ≤ 10^{9}$
 
Subtask #4 : (45 points) 

$Original constraints$

------ Example ------ 

Input:
5
0 1 0 0 0
0 0 1 1 0
1 0 0 0 0
0 0 0 1 0
0 0 0 0 0
4
3 1
10000 1
0 5
1 5

Output:
2
1 4
2
2 4
1
5
0
-1

Source: codechef | Difficulty: VERY_HARD
Tags: Bit manipulation

Graph algorithms

Range queries

Mathematics

Tree queries


Solutions:
import queue
import math
n = int(input())
adj = []
cost = []
for i in range(n):
	l = []
	l = map(int, input().split())
	l = list(l)
	adj.append(l)
al = []
for i in range(n):
	al.append([])
	for j in range(n):
		if adj[i][j] == 1:
			al[i].append(j)
q = int(input())
tot = dict()
totc = dict()
qout = dict()
for _ in range(q):
	(k, x) = map(int, input().split())
	q1 = queue.Queue()
	q2 = queue.Queue()
	u = x - 1
	if u in tot:
		tunit = dict()
		tunit = tot[u]
		tcycle = []
		if u in totc:
			tcycle = totc[u]
		if k in tunit:
			print(len(tunit[k]))
			print(' '.join((str(j + 1) for j in tunit[k])))
		else:
			ln = len(tunit)
			lnc = len(tcycle)
			z = k - ln + 1
			if lnc > 0:
				z = z % lnc
				if z == 0:
					z = lnc - 1
				else:
					z = z - 1
				print(len(tcycle[z]))
				print(' '.join((str(j + 1) for j in tcycle[z])))
			else:
				print(0)
				print(-1)
		continue
	q1.put(u)
	y = 0
	count = 0
	unit = dict()
	ind = []
	xl = []
	xl.append(u)
	ind.append(xl)
	unit[count] = xl
	q1l = []
	q2l = []
	q1l.append(u)
	while True:
		if y % 2 == 0:
			vis = [0] * n
			flag = 0
			xl = []
			q2l = []
			tq1l = tuple(q1l)
			if tq1l in qout:
				q2l = qout[tq1l]
				xl = qout[tq1l]
				flag = 1
			else:
				while q1.empty() == False:
					u = q1.get()
					for w in al[u]:
						vis[w] = 1
						flag = 1
				for i in range(n):
					if vis[i] == 1:
						xl.append(i)
						q2.put(i)
						q2l.append(i)
			if len(xl) != 0:
				qout[tq1l] = xl
			count = count + 1
			if flag == 0:
				break
			if xl in ind:
				break
			unit[count] = xl
			ind.append(xl)
		else:
			vis = [0] * n
			flag = 0
			xl = []
			q1l = []
			tq2l = tuple(q2l)
			if tq2l in qout:
				q1l = qout[tq2l]
				xl = qout[tq2l]
				flag = 1
			else:
				while q2.empty() == False:
					u = q2.get()
					for w in al[u]:
						vis[w] = 1
						flag = 1
				for i in range(n):
					if vis[i] == 1:
						xl.append(i)
						q1.put(i)
						q1l.append(i)
			count = count + 1
			if len(xl) != 0:
				qout[tq2l] = xl
			if flag == 0:
				break
			if xl in ind:
				break
			unit[count] = xl
			ind.append(xl)
		y = y + 1
	tot[x - 1] = unit
	cycle = []
	if xl in ind:
		index = ind.index(xl)
		cycle = []
		cycle = ind[index:]
		totc[x - 1] = cycle
	if k in unit:
		print(len(unit[k]))
		print(' '.join((str(j + 1) for j in unit[k])))
	else:
		ln = len(unit)
		lnc = len(cycle)
		z = k - ln + 1
		if lnc > 0:
			z = z % lnc
			if z == 0:
				z = lnc - 1
			else:
				z = z - 1
			print(len(cycle[z]))
			print(' '.join((str(j + 1) for j in cycle[z])))
		else:
			print(0)
			print(-1)


import numpy as np

def getPowers(x):
	k = 2
	ret = [x]
	done = False
	while k < 10 ** 9:
		if done:
			ret += [x]
		else:
			y = x.dot(x)
			y[y > 0] = 1
			done = np.all(y == x)
			x = y
			ret += [x]
		k *= 2
	return ret

def mpow(xp, z, k):
	i = 0
	while k > 0:
		if k % 2 == 1:
			z = xp[i].dot(z)
		i = i + 1
		k //= 2
	return z

def solve(x, y):
	xp = getPowers(x)
	n = x.shape[0]
	for (k, z) in y:
		z0 = np.zeros(n)
		z0[z] = 1
		z0 = mpow(xp, z0, k)
		ret = list(np.where(z0 > 0)[0])
		print(len(ret))
		if len(ret) == 0:
			print(-1)
		else:
			print(' '.join((str(x + 1) for x in ret)))
import sys
f = sys.stdin
n = int(f.readline())
x = []
for j in range(n):
	y = list(map(int, f.readline().split()))
	x += [y]
x = np.array(x, dtype=np.float64).transpose()
m = int(f.readline())
y = []
for i in range(m):
	(a, b) = map(int, f.readline().split())
	y += [(a, b - 1)]
solve(x, y)