You are given a book with $n$ chapters.

Each chapter has a specified list of other chapters that need to be understood in order to understand this chapter. To understand a chapter, you must read it after you understand every chapter on its required list.

Currently you don't understand any of the chapters. You are going to read the book from the beginning till the end repeatedly until you understand the whole book. Note that if you read a chapter at a moment when you don't understand some of the required chapters, you don't understand this chapter.

Determine how many times you will read the book to understand every chapter, or determine that you will never understand every chapter no matter how many times you read the book.


-----Input-----

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 2\cdot10^4$).

The first line of each test case contains a single integer $n$ ($1 \le n \le 2\cdot10^5$) — number of chapters.

Then $n$ lines follow. The $i$-th line begins with an integer $k_i$ ($0 \le k_i \le n-1$) — number of chapters required to understand the $i$-th chapter. Then $k_i$ integers $a_{i,1}, a_{i,2}, \dots, a_{i, k_i}$ ($1 \le a_{i, j} \le n, a_{i, j} \ne i, a_{i, j} \ne a_{i, l}$ for $j \ne l$) follow — the chapters required to understand the $i$-th chapter.

It is guaranteed that the sum of $n$ and sum of $k_i$ over all testcases do not exceed $2\cdot10^5$.


-----Output-----

For each test case, if the entire book can be understood, print how many times you will read it, otherwise print $-1$.


-----Examples-----

Input
5
4
1 2
0
2 1 4
1 2
5
1 5
1 1
1 2
1 3
1 4
5
0
0
2 1 2
1 2
2 2 1
4
2 2 3
0
0
2 3 2
5
1 2
1 3
1 4
1 5
0
Output
2
-1
1
2
5


-----Note-----

In the first example, we will understand chapters $\{2, 4\}$ in the first reading and chapters $\{1, 3\}$ in the second reading of the book.

In the second example, every chapter requires the understanding of some other chapter, so it is impossible to understand the book.

In the third example, every chapter requires only chapters that appear earlier in the book, so we can understand everything in one go.

In the fourth example, we will understand chapters $\{2, 3, 4\}$ in the first reading and chapter $1$ in the second reading of the book.

In the fifth example, we will understand one chapter in every reading from $5$ to $1$.

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Graph algorithms

Sorting

Implementation

Complete search

Dynamic programming

Data structures


Solutions:
import sys, heapq
for _ in range(int(sys.stdin.readline())):
	n = int(sys.stdin.readline())
	d = [[] for i in range(n)]
	h = []
	l = []
	for i in range(n):
		y = [int(i) for i in sys.stdin.readline().split()]
		l.append(y[0])
		if y[0] == 0:
			heapq.heappush(h, i)
		for j in range(1, y[0] + 1):
			d[y[j] - 1].append(i)
	c = t = 0
	while h:
		i = heapq.heappop(h)
		t += 1
		c = i // n
		i = i % n
		for j in d[i]:
			l[j] -= 1
			if l[j] == 0:
				heapq.heappush(h, j + c * n if j > i else j + n + c * n)
	sys.stdout.write('%d\n' % (c + 1 if t == n else -1))


import sys
input = sys.stdin.readline

def solve():
	n = int(input())
	arr = [list(map(int, input().split())) for _ in range(n)]
	graph = [[] for _ in range(n)]
	incoming = [0] * n
	vals = [1] * n
	for i in range(n):
		for j in range(1, len(arr[i])):
			incoming[i] += 1
			graph[arr[i][j] - 1].append(i)
	q = []
	ordering = []
	for i in range(n):
		if incoming[i] == 0:
			q.append(i)
	while q:
		node = q.pop()
		ordering.append(node)
		for nei in graph[node]:
			incoming[nei] -= 1
			vals[nei] = max(vals[nei], vals[node] + 1 if nei < node else vals[node])
			if incoming[nei] == 0:
				q.append(nei)
	return -1 if len(ordering) < n else max(vals)
for _ in range(int(input())):
	print(solve())


from heapq import *
t = int(input())
for _ in range(t):
	n = int(input())
	b = [[] for i in range(n + 1)]
	d = [0 for i in range(n + 1)]
	for i in range(1, n + 1):
		l = list(map(int, input().split()))
		d[i] = l[0]
		for j in l[1:]:
			b[j].append(i)
	count = 0
	cursum = sum(d)
	if cursum == 0:
		print(1)
	else:
		possible = True
		canread = []
		for i in range(1, n + 1):
			if d[i] == 0:
				heappush(canread, i)
		while True:
			if len(canread) == 0:
				break
			count += 1
			nextread = []
			while len(canread) > 0:
				x = heappop(canread)
				for c in b[x]:
					d[c] -= 1
					if d[c] == 0:
						if c > x:
							heappush(canread, c)
						else:
							heappush(nextread, c)
			canread = nextread
		print(count if sum(d) == 0 else -1)


from collections import deque
import heapq

def inp():
	n = int(input())
	reqs = [0 for _ in range(n + 1)]
	affects = [[] for _ in range(n + 1)]
	for i in range(1, n + 1):
		temp = list(map(int, input().split()))
		if temp[0] == 0:
			continue
		reqs[i] = temp[0]
		for chapter in temp[1:]:
			affects[chapter].append(i)
	return (reqs, affects, n)

def solve(reqs, affects, n):
	to_read = [i for i in range(1, n + 1) if not reqs[i]]
	heapq.heapify(to_read)
	chapters_read = 0
	count = 0
	cur = 0
	while to_read:
		next_read = []
		while to_read:
			next_chapter = heapq.heappop(to_read)
			reqs[next_chapter] = -1
			chapters_read += 1
			for affected in affects[next_chapter]:
				reqs[affected] -= 1
				if not reqs[affected] and affected > next_chapter:
					heapq.heappush(to_read, affected)
				elif not reqs[affected]:
					next_read.append(affected)
		count += 1
		to_read = next_read
		heapq.heapify(to_read)
	if chapters_read == n:
		return count
	else:
		return -1
t = int(input())
for _ in range(t):
	(reqs, affects, n) = inp()
	ans = solve(reqs, affects, n)
	print(ans)


def solve(_num=0):
	n = int(input())
	chapters = []
	c___deps = [[] for _ in range(n)]
	for i in range(n):
		c = [int(x) - 1 for x in input().split()]
		c.pop(0)
		for neigh in c:
			c___deps[neigh].append(i)
		chapters.append(c)
	stack = []
	c___rnr = [0 for _ in range(n)]
	c___ans = [-1 for _ in range(n)]
	for (i, c) in enumerate(chapters):
		if c___rnr[i] == len(c):
			stack.append(i)
			c___ans[i] = 1
	while stack:
		curr = stack.pop()
		for dep in c___deps[curr]:
			c___rnr[dep] += 1
			if c___rnr[dep] == len(chapters[dep]):
				ans = -1
				for dd in chapters[dep]:
					ca = c___ans[dd]
					if dd > dep:
						ca += 1
					ans = max(ca, ans)
				c___ans[dep] = ans
				stack.append(dep)
	if -1 in c___ans:
		print(-1)
	else:
		print(max(c___ans))
for i in range(int(input())):
	solve(i)


t = int(input())
while t:
	n = int(input())
	ct = [1] * n
	pre_req = [0] * n
	dt = {i: [] for i in range(n)}
	queue = []
	for j in range(n):
		a = list(map(int, input().split()))
		for i in range(1, a[0] + 1):
			dt[a[i] - 1].append(j)
		pre_req[j] = a[0]
		if a[0] == 0:
			queue += [j]
	ind = 0
	while ind < len(queue):
		g = queue[ind]
		for i in dt[g]:
			pre_req[i] -= 1
			ct[i] = max(ct[i], ct[g] + [0, 1][i < g])
			if pre_req[i] == 0:
				queue.append(i)
		ind += 1
	if max(pre_req) != 0:
		print(-1)
	else:
		print(max(ct))
	t -= 1


import sys
input = sys.stdin.readline
for i in range(int(input())):
	n = int(input())
	l = [1] * n
	d = {i: [] for i in range(n)}
	q = []
	m = [0] * n
	for j in range(n):
		a = [*map(int, input().split())]
		for i in range(1, a[0] + 1):
			d[a[i] - 1].append(j)
		m[j] = a[0]
		if a[0] == 0:
			q += [[a[0], j]]
	y = 0
	while y < len(q):
		g = q[y]
		for i in d[g[1]]:
			m[i] -= 1
			l[i] = max(l[i], l[g[1]] + [0, 1][i < g[1]])
			if m[i] == 0:
				q += [[0, i]]
		y += 1
	if max(m) != 0:
		print(-1)
	else:
		print(max(l))


from collections import defaultdict
from heapq import heappush, heappop
t = int(input().strip())
inputs = []
for _ in range(t):
	n = int(input().strip())
	prereqs = []
	for _ in range(n):
		ls = list(map(int, input().strip().split()))
		prereqs.append(ls)
	inputs.append((n, prereqs))
for (n, prereqs) in inputs:
	required = [0] * (n + 1)
	required_by = defaultdict(list)
	for i in range(1, n + 1):
		for p in prereqs[i - 1][1:]:
			required_by[p].append(i)
			required[i] += 1
	q = []
	for i in range(1, n + 1):
		if required[i] == 0:
			heappush(q, i)
	if not q:
		print(-1)
		continue
	read_count = 0
	ans = 0
	next_q = []
	while q:
		i = heappop(q)
		read_count += 1
		for j in required_by[i]:
			required[j] -= 1
			if required[j] != 0:
				continue
			if j > i:
				heappush(q, j)
			else:
				heappush(next_q, j)
		if not q:
			q = next_q
			next_q = []
			ans += 1
	if read_count < n:
		print(-1)
	else:
		print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	l = [1] * n
	d = {i: [] for i in range(n)}
	q = []
	m = [0] * n
	for j in range(n):
		a = [*map(int, input().split())]
		for i in range(1, a[0] + 1):
			d[a[i] - 1].append(j)
		m[j] = a[0]
		if a[0] == 0:
			q += [[a[0], j]]
	y = 0
	while y < len(q):
		g = q[y]
		for i in d[g[1]]:
			m[i] -= 1
			l[i] = max(l[i], l[g[1]] + [0, 1][i < g[1]])
			if m[i] == 0:
				q += [[0, i]]
		y += 1
	if max(m) != 0:
		print(-1)
	else:
		print(max(l))


def func2(datalist, n):
	fished = [0] * (n + 1)
	sid = 1
	eid = 1
	xlist = [[]]
	children = [[] for i in range(n + 1)]
	xn = 0
	for i in range(1, n + 1):
		if datalist[i][0] == 0:
			fished[eid] = i
			eid += 1
			xlist.append([1, 0])
			xn += 1
		else:
			for id in datalist[i][1:]:
				children[id].append(i)
			xlist.append([1, datalist[i][0]])
	maxstep = 1
	while sid != eid:
		cid = fished[sid]
		sid += 1
		for id in children[cid]:
			xlist[id][1] -= 1
			if cid < id:
				xlist[id][0] = max(xlist[id][0], xlist[cid][0])
			else:
				xlist[id][0] = max(xlist[id][0], xlist[cid][0] + 1)
			if xlist[id][1] == 0:
				xn += 1
				maxstep = max(maxstep, xlist[id][0])
				if children[id]:
					fished[eid] = id
					eid += 1
	if xn != n:
		return -1
	return maxstep
t = int(input())
for i in range(t):
	n = int(input())
	datalist = [0]
	for i in range(n):
		datalist.append([int(x) for x in input().split()])
	print(func2(datalist, n))


from collections import defaultdict as dd, deque
import sys
input = sys.stdin.readline

def check_cycle(g, indegree, n):
	c = 0
	d = deque([])
	ans = dd(lambda : 1)
	for i in range(n):
		if indegree[i + 1] == 0:
			d.append(i + 1)
	while d:
		u = d.popleft()
		c += 1
		for v in g[u]:
			indegree[v] -= 1
			if v < u:
				ans[v] = max(ans[v], ans[u] + 1)
			else:
				ans[v] = max(ans[v], ans[u])
			if indegree[v] == 0:
				d.append(v)
	if c != n:
		return False
	if ans:
		return max(ans.values())
	return 1
for _ in range(int(input())):
	n = int(input())
	g = dd(set)
	indegree = dd(int)
	for i in range(n):
		a = list(map(int, input().split()))
		for j in range(1, a[0] + 1):
			indegree[i + 1] += 1
			g[a[j]].add(i + 1)
	res = check_cycle(g, indegree, n)
	if res == False:
		print(-1)
	else:
		print(res)


from collections import defaultdict, deque

def book_turn(indegree, graph):
	queue = deque([(x, 1) for x in indegree if indegree[x] == 0])
	if not queue:
		return -1
	visited = set(queue)
	(turns, read_chapters) = (0, 0)
	chapter_turns = [0 for _ in range(len(indegree))]
	while queue:
		for _ in range(len(queue)):
			(node, turn) = queue.popleft()
			read_chapters += 1
			turns = max(turns, turn)
			for neighbour in graph[node]:
				indegree[neighbour] -= 1
				cur_turn = turn if neighbour > node else turn + 1
				chapter_turns[neighbour - 1] = max(chapter_turns[neighbour - 1], cur_turn)
				if indegree[neighbour] == 0:
					queue.append((neighbour, chapter_turns[neighbour - 1]))
	if read_chapters != len(indegree):
		return -1
	return turns
t = int(input())
for _ in range(t):
	n = int(input())
	indegree = defaultdict(int)
	graph = defaultdict(set)
	for i in range(1, n + 1):
		dependent = list(map(int, input().split()))
		if dependent[0] == 0:
			indegree[i] = 0
		for j in range(1, len(dependent)):
			indegree[i] += 1
			graph[dependent[j]].add(i)
	print(book_turn(indegree, graph))


from collections import deque
for _ in range(int(input())):
	n = int(input())
	rl = {}
	l = {i: [] for i in range(1, n + 1)}
	q = deque([])
	kl = {}
	vist = {i: False for i in range(1, n + 1)}
	for i in range(1, n + 1):
		t = list(map(int, input().split()))
		rl[i] = t[1:]
		for j in rl[i]:
			l[j].append(i)
		if t[0] == 0:
			q.append(i)
		kl[i] = t[0]
	topo = []
	while len(q) != 0:
		u = q[0]
		q.popleft()
		vist[u] = True
		topo.append(u)
		for v in l[u]:
			if kl[v] - 1 == 0:
				q.append(v)
			kl[v] -= 1
	f = 0
	for i in range(1, n + 1):
		if vist[i] == False:
			f = 1
			break
	if f == 1:
		print(-1)
		continue
	dp = [1] * (n + 1)
	ans = 0
	for i in topo:
		for j in rl[i]:
			if i > j:
				dp[i] = max(dp[i], dp[j])
			else:
				dp[i] = max(dp[i], dp[j] + 1)
		ans = max(ans, dp[i])
	print(ans)