The country of Chefland is a group of N cities having M directed roads between its cities. It takes 1 second to travel on any road. 

Chef has decided to travel through this country. His travel plan goes as follows - 

He will randomly choose a starting city.
While there are outgoing roads in his current city, he will randomly choose one of them and travel it. He can choose roads he has already traveled through and visit cities multiple times.
He will stop if there are no outgoing roads in the current city or N seconds have passed. 

Chef will be disappointed if after traveling he does not end up in the capital city.

The ministers have not yet decided upon the capital city. They would like to choose it in such a way that Chef is not disappointed by his trip. To make their decision a bit easier, they can build some new roads between cities.

Find the minimum number of roads that need to be built such that the ministers can choose a capital city that doesn't disappoint Chef no matter where his trip starts or how it progresses.

It is possible that the current road system is such that no matter which roads are added, a capital that doesn't disappoint Chef cannot be chosen. In this case, print -1 instead.

------ Input Format ------ 

- The first line will contain T, denoting the number of test cases. The description of T test cases follows.
- The first line of each test case contains a single integer N, denoting the number of cities.
- The second line of each test case contains a single integer M, denoting the number of roads in the city initially.
- Then M lines follow each containing two integers A and B, denoting a road from city A to city B.

------ Output Format ------ 

For each test case, output a single line denoting the minimum number of roads you have to build, or -1 if it is not possible to satisfy the given condition.

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

$1 ≤ T ≤ 5\cdot 10^{4}$
$1 ≤ N ≤ 2\cdot 10^{5}$
$0 ≤ M ≤ \min(N\cdot (N - 1), 4\cdot 10^{5})$
- The sum of $N + M$ does not exceed $10^{6}$ over all testcases
- The graph has no self loops or duplicate edges

----- Sample Input 1 ------ 
2
3
2
1 2
2 3
2
2
1 2
2 1

----- Sample Output 1 ------ 
0
-1
----- explanation 1 ------ 
Test case $1$: No matter where Chef starts, he will end up in city $3$, so it can be made the capital city and we do not need to construct any roads.

Test case $2$: No new roads can be constructed. Chef will always end up in whichever city he starts from, so the ministers cannot decide upon a capital — choosing city $1$ as the capital would disappoint Chef if his trip started from city $2$ and vice versa.

Difficulty: VERY_HARD
Tags: Graph algorithms

Directed graphs

Starter code:

Solutions:
from collections import deque

def topoSort(V, adj):
	q = deque()
	indegree = [0] * (V + 1)
	for i in range(1, V + 1):
		for j in adj[i]:
			indegree[j] += 1
	for i in range(1, V + 1):
		if indegree[i] == 0:
			q.append(i)
	arr = []
	while q:
		node = q.popleft()
		indegree[node] -= 1
		arr.append(node)
		for k in adj[node]:
			indegree[k] -= 1
			if indegree[k] == 0:
				q.append(k)
	for i in indegree:
		if i > 0:
			return False
	return True

def solve(n, m, adj):
	ans = 0
	if topoSort(n, adj):
		for i in range(1, len(adj)):
			if len(adj[i]) == 0:
				ans += 1
		ans -= 1
		return ans
	return -1
for test in range(int(input())):
	n = int(input())
	m = int(input())
	adj = []
	for i in range(n + 1):
		adj.append([])
	for i in range(m):
		(x, y) = map(int, input().split())
		adj[x].append(y)
	print(solve(n, m, adj))


def dfs(graph, cr, vi, st):
	vi[cr] = st[cr] = True
	for i in graph.get(cr, []):
		if st[i]:
			return True
		if vi[i]:
			continue
		if dfs(graph, i, vi, st):
			return True
	st[cr] = False
	return False

def hascycle(graph, n):
	vi = [False] * n
	st = [False] * n
	for i in range(n):
		if vi[i]:
			continue
		if dfs(graph, i, vi, st):
			return True
	return False
t = int(input())
for _ in range(t):
	n = int(input())
	e = int(input())
	graph = {}
	for i in range(e):
		(l, r) = map(int, input().split())
		graph[l - 1] = graph.get(l - 1, []) + [r - 1]
	if hascycle(graph, n):
		print(-1)
		continue
	count = 0
	for i in range(n):
		if not graph.get(i, []):
			count += 1
	print(count - 1)


for _ in range(int(input())):
	n = int(input())
	m = int(input())
	d = [[] for i in range(n + 1)]
	inc = [0 for i in range(n + 1)]
	for i in range(m):
		(a, b) = map(int, input().split())
		d[a].append(b)
		inc[b] += 1
	c = 0
	ans = 0
	q = list()
	for i in range(1, n + 1):
		if inc[i] == 0:
			q.append(i)
		if len(d[i]) == 0:
			ans += 1
	while len(q) > 0:
		c += 1
		i = q.pop(0)
		for x in d[i]:
			inc[x] -= 1
			if inc[x] == 0:
				q.append(x)
	if c != n:
		print(-1)
	else:
		print(ans - 1)


from math import inf
from collections import *
import math, os, sys, heapq, bisect, random, threading
from functools import lru_cache
from itertools import *

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def inpu():
	return int(inp())

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def fsep():
	return map(float, inp().split())
(M, M1) = (1000000007, 998244353)

def dfs(curr, col, d):
	col[curr] = 1
	for j in d[curr]:
		if col[j] == 0:
			if dfs(j, col, d):
				return True
		elif col[j] == 1:
			return True
	col[curr] = 2
	return False

def main():
	how_much_noob_I_am = 1
	how_much_noob_I_am = inpu()
	for _ in range(1, how_much_noob_I_am + 1):
		n = inpu()
		m = inpu()
		d = defaultdict(list)
		for i in range(m):
			(a, b) = sep()
			d[a].append(b)
		col = [0] * (n + 1)
		for i in range(1, n + 1):
			if col[i] == 0:
				if dfs(i, col, d):
					print(-1)
					break
		else:
			ans = 0
			for i in range(1, n + 1):
				if len(d[i]) == 0:
					ans += 1
			print(ans - 1)
main()


import collections
testcase = int(input())
while testcase:
	testcase -= 1
	n = int(input())
	m = int(input())
	graph = []
	for i in range(n + 1):
		graph.append([])
	for i in range(m):
		(a, b) = map(int, input().split())
		graph[a].append(b)
	q = []
	indegree = [0] * (n + 1)
	for i in range(1, n + 1):
		for j in graph[i]:
			indegree[j] += 1
	for i in range(1, n + 1):
		if indegree[i] == 0:
			q.append(i)
	ct = 0
	while q:
		x = q.pop()
		ct += 1
		for it in graph[x]:
			indegree[it] -= 1
			if indegree[it] == 0:
				q.append(it)
	if ct != n:
		print(-1)
	else:
		ans = 0
		for i in range(1, n + 1):
			if len(graph[i]) == 0:
				ans += 1
		print(ans - 1)


import collections
t = int(input())
while t:
	t -= 1
	n = int(input())
	m = int(input())
	graph = collections.defaultdict(set)
	for i in range(m):
		(a, b) = map(int, input().split())
		graph[a].add(b)
	q = []
	indegree = [0] * (n + 1)
	for i in range(1, n + 1):
		for j in graph[i]:
			indegree[j] += 1
	for i in range(1, n + 1):
		if indegree[i] == 0:
			q.append(i)
	ct = 0
	while q:
		x = q.pop()
		ct += 1
		for k in graph[x]:
			indegree[k] -= 1
			if indegree[k] == 0:
				q.append(k)
	if ct == n:
		ans = 0
		for i in range(1, n + 1):
			if len(graph[i]) == 0:
				ans += 1
		print(ans - 1)
	else:
		print(-1)