There are $N$ people working in a building, and each one works in a separate cabin. Chef’s employees are numbered by integers from $1$ to $N$, inclusive. Chef wants to ensure the safety of his employees. He wants to have fire escapes in the building and wants to train the employees to use these by conducting mock drills.

Chef knows that the number of people working in his office can be very large. In order to avoid crowding of a common fire escape route during emergency, Chef has decided to build multiple fire escapes. For the safety of every employee, each cabin has a fire exit which is connected to one of the fire escape routes.

A lot of employees are friends with each other. The friendship is mutual. This means that if employee $i$ is a friend of employee $j$ then employee $j$ is a friend of employee $i$ as well. But friendship is NOT necessarily transitive. This means that if employee $i$ is a friend of employee $j$ AND employee $j$ is a friend of employee $k$, then employee $i$ and employee $k$ need not necessarily be friends.

If two employees are friends, they do not want to escape through different routes.
This complicates the task for the Chef. As already mentioned, he wants to have the maximum number of fire escape routes to ensure maximum safety. Also, for every escape route, one of the employees using that route needs to be appointed as the fire drill captain. The captain will be responsible for conducting the mock drills and train all the employees using that route. Your task is simple. Given the number of employees and the friendship list, you need to tell the Chef the maximum number of fire escape routes that he can have in the building and the number of ways of selecting the captains for every route. Since the number of ways can be really large, output this value modulo $10^{9} + 7$.

------  Input ------
The first line of the input contains a single integer $T$, denoting the number of test cases. The description of T test cases follows. 
The first line of each test case contains two space-separated integers $N$ and $M$, denoting the number of employees and the number of friendship relations, respectively.
Each of the following $M$ lines contains two space-separated integers $i$ and $j$, denoting that employee $i$ and employee $j$ are friends.

------  Output ------
For each test case, output a single line containing two space separated integers, denoting the maximum number of distinct fire escape routes that can be constructed and the number of ways of selecting the captains modulo $10^{9} + 7$.

------  Constraints ------
$1 ≤ T ≤ 5$
$1 ≤ N ≤ 10^{5}$
$0 ≤ M ≤ 10^{5}$
$1 ≤ i, j ≤ N$
$ i \neq j$
For any pair of employees $i$ and $j$ such that $1 ≤ i, j ≤ N$, at most one pair among $(i, j)$ and $(j, i)$ will appear in the input

----- Sample Input 1 ------ 
3
4 2
1 2
2 3
5 3
1 2
2 3
1 3
6 3
1 2
3 4
5 6
----- Sample Output 1 ------ 
2 3
3 3
3 8
----- explanation 1 ------ 
Example case 1: Here employees $1$ and $2$ are friends and should share the same fire escape. Also employees $2$ and $3$ share the same fire escape. This means employees $1$, $2$, and $3$ will have a common route. But to maximize number of routes Chef could assign another route to employee $4$ since it is not a friend of other employee. So we have two escape routes with the following distribution of employees by routes: $\{1, 2, 3\}$, $\{4\}$. Therefore, there are $3$ ways to chose drill captains: $(1, 4)$, $(2, 4)$, $(3, 4)$, where first element in the pair denotes the captain for the first route and second element denotes the captain for the second route.

Example case 2: Here the optimal distribution of employees by routes is $\{1, 2, 3\}$, $\{4\}$, $\{5\}$. Therefore, there are $3$ ways to chose drill captains: $(1, 4, 5)$, $(2, 4, 5)$, $(3, 4, 5)$.

Example case 3: Here the optimal distribution of employees by routes is $\{1, 2\}$, $\{3, 4\}$, $\{5, 6\}$. Therefore, there are 8 ways to chose drill captains: $(1, 3, 5)$, $(1, 3, 6)$, $(1, 4, 5)$, $(1, 4, 6)$, $(2, 3, 5)$, $(2, 3, 6)$, $(2, 4, 5)$, $(2, 4, 6)$.

Source: codechef | Difficulty: MEDIUM_HARD
Tags: Spanning trees

Combinatorics

Data structures

Mathematics


Solutions:
def f(a):
	if p[a] < 0:
		return a
	p[a] = f(p[a])
	return p[a]

def u(a, b):
	a = f(a)
	b = f(b)
	if a == b:
		return
	if p[a] < p[b]:
		p[a] += p[b]
		p[b] = a
	else:
		p[b] += p[a]
		p[a] = b
for _ in range(int(input())):
	(n, r) = [int(x) for x in input().split()]
	p = [-1] * (n + 1)
	for i in range(r):
		(a, b) = [int(x) for x in input().split()]
		u(a, b)
	ans = 1
	count = 0
	for i in range(1, n + 1):
		if p[i] < 0:
			count += 1
			ans = ans * (-1 * p[i]) % (10 ** 9 + 7) % (10 ** 9 + 7)
	print(count, ans)


def find(a):
	if parent[a] < 0:
		return a
	parent[a] = find(parent[a])
	return parent[a]

def union(a, b):
	a = find(a)
	b = find(b)
	if a == b:
		return
	if parent[a] < parent[b]:
		parent[a] += parent[b]
		parent[b] = a
	else:
		parent[b] += parent[a]
		parent[a] = b
for _ in range(int(input())):
	(n, r) = [int(x) for x in input().split()]
	parent = [-1] * (n + 1)
	for i in range(r):
		(a, b) = [int(x) for x in input().split()]
		union(a, b)
	ans = 1
	count = 0
	for i in range(1, n + 1):
		if parent[i] < 0:
			count += 1
			ans = ans * (-1 * parent[i]) % (10 ** 9 + 7) % (10 ** 9 + 7)
	print(count, ans)


t = int(input())
while t:
	t -= 1
	(n, m) = list(map(int, input().split(' ')))
	n += 1
	edge = {}
	visited = [False for i in range(n)]
	for i in range(n):
		edge[i] = []
	for i in range(m):
		(x, y) = list(map(int, input().split(' ')))
		edge[x].append(y)
		edge[y].append(x)
	group = []
	captain = pow(10, 9) + 7
	totalcount = 0
	for i in range(1, n):
		if visited[i]:
			continue
		totalcount += 1
		if not edge[i]:
			group.append(1)
			continue
		count = 0
		q = []
		q.append(i)
		visited[i] = True
		while q:
			item = q.pop(0)
			count += 1
			for x in edge[item]:
				if not visited[x]:
					q.append(x)
					visited[x] = True
		group.append(count)
	if group:
		result = 1
		for x in group:
			result = result % captain * (x % captain)
		result = result % captain
	else:
		result = 0
	print(totalcount, ' ', result)


import sys
from math import sqrt, gcd, factorial, ceil, floor, pi
from collections import deque, Counter, OrderedDict
from heapq import heapify, heappush, heappop
sys.setrecursionlimit(10 ** 6)
input = lambda : sys.stdin.readline()
I = lambda : int(input())
S = lambda : input().strip()
M = lambda : map(int, input().strip().split())
L = lambda : list(map(int, input().strip().split()))
mod = 10 ** 9 + 7

def dfs(node):
	st = [node]
	v[node] = 1
	ans = 0
	while st:
		cur = st.pop()
		ans += 1
		for i in adj[cur]:
			if not v[i]:
				st.append(i)
				v[i] = 1
	return ans
for _ in range(I()):
	(n, m) = M()
	adj = {i + 1: [] for i in range(n)}
	for i in range(m):
		(p, q) = M()
		adj[p].append(q)
		adj[q].append(p)
	v = [0] * (n + 1)
	(a1, a2) = (0, 1)
	for i in range(n):
		if not v[i + 1]:
			a1 += 1
			a2 *= dfs(i + 1)
			a2 %= mod
	print(a1, a2)


from collections import defaultdict
from sys import setrecursionlimit
setrecursionlimit(int(1000000000.0))

def dfs(node):
	vis[node] = True
	cnt = 1
	for child in graph[node]:
		if vis[child] == False:
			cnt += dfs(child)
	return cnt
mod = int(1000000000.0) + 7
for _ in range(int(input())):
	(V, e) = map(int, input().split())
	graph = defaultdict(list)
	vis = [False] * (V + 1)
	for _ in range(e):
		(u, v) = map(int, input().split())
		graph[u].append(v)
		graph[v].append(u)
	ans = 1
	cnt = 0
	for node in range(1, V + 1):
		if vis[node] == False:
			cnt += 1
			nodes = dfs(node)
			ans = ans * nodes % mod
	print(cnt, ans)


from collections import defaultdict
from collections import Counter
import sys, threading
sys.setrecursionlimit(10 ** 6)

class dsu:

	def __init__(self, n):
		self.parent = [i for i in range(n)]
		self.size = [1] * n

	def find(self, x):
		if x != self.parent[x]:
			self.parent[x] = self.find(self.parent[x])
		return self.parent[x]

	def union(self, u, v):
		(u, v) = (self.find(u), self.find(v))
		if u != v:
			if self.size[u] < self.size[v]:
				(u, v) = (v, u)
			self.size[u] += self.size[v]
			self.size[v] = 0
			self.parent[v] = u

	def cout(self):
		mp = defaultdict(int)
		for i in range(n):
			mp[self.find(i)] += 1
		return mp

def setbit(arr):
	mask = 1
	bit = [0] * 32
	for i in range(32):
		for k in arr:
			if k & mask:
				bit[i] += 1
		mask <<= 1
	return bit

def prefix_sum(nums):
	prefix = [0]
	for i in range(len(nums)):
		prefix.append(prefix[-1] + nums[i])
	return prefix

def mx_lensubarray(nums):
	res = 0
	j = 0
	mp = defaultdict(int)
	prefix = prefixsum(nums)
	mxSum = 0
	for i in range(len(nums)):
		if nums[i] in mp:
			temp = mp[nums[i]]
		else:
			temp = 0
		j = max(temp, j)
		mp[nums[i]] = i + 1
		res = max(res, i - j + 1)
		mxSum = max(mxSum, prefix[i + 1] - prefix[j])
	return res

def lenOfLongSubarr(self, A, N, k):
	mp = {}
	sm = 0
	mxlen = 0
	for i in range(N):
		sm += A[i]
		if sm == k:
			mxlen = i + 1
		if sm - k in mp:
			mxlen = max(mxlen, i - mp[sm - k])
		if sm not in mp:
			mp[sm] = i
	return mxlen

def no_of_factor(s):
	cnt = 0
	x = int(s ** 0.5)
	for i in range(1, x + 1):
		if not s % i:
			cnt = cnt + 1 if s / i == i else cnt + 2
		i += 1
	return cnt

def primes(n):
	arr = []
	i = 2
	while i * i <= n:
		if not n % i:
			cnt = 0
			while not n % i:
				cnt += 1
				n //= i
			arr.append([i, cnt])
		i += 1
	if n > 1:
		arr.append([n, 1])
	return arr

def sieve(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	res = []
	for i in range(2, n + 1):
		if prime[i]:
			res.append(i)
	return res

def treeinput(n, m):
	global adj
	adj = [[] for i in range(n + 1)]
	for i in range(m):
		(u, v) = map(int, input().split())
		adj[u].append(v)
		adj[v].append(u)

def dfs(node, parent):
	vis[node] = 1
	sz = 1
	for child in adj[node]:
		if vis[child] == 0 and node != parent:
			sz += dfs(child, node)
	return sz

def dfs_size(node, parent):
	sum_size[node] = 1
	for child in adj[node]:
		if child != parent:
			dfs_size(child, node)
			sum_size[node] += sum_size[child]

def anda(arr):
	res = arr[0]
	for i in arr:
		res &= i
	return res

def ora(arr):
	res = arr[0]
	for i in arr:
		res |= i
	return res

def xora(arr):
	res = 0
	for i in arr:
		res ^= i
	return res
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	vis = [0] * (n + 1)
	cnt = 0
	treeinput(n, m)
	res = 1
	for i in range(1, n + 1):
		if not vis[i]:
			sz = dfs(i, -1)
			cnt += 1
			res = res * sz % 1000000007
	print(cnt, res)


from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(1000000000)
mod = 1000000007

def integer_list():
	return list(map(int, input().split()))

def dfs(node):
	childs = graph[node]
	ans = 0
	for child in childs:
		if child not in visited:
			visited.add(child)
			x = dfs(child)
			ans += 1 + x
	return ans

def main():
	try:
		pairs = []
		for i in range(1, n + 1):
			if i not in graph:
				graph[i].append(i)
			if i not in visited:
				visited.add(i)
				x = dfs(i)
				pairs.append(x + 1)
		ans1 = len(pairs)
		ans2 = 1
		for ele in pairs:
			ans2 *= ele
			ans2 %= mod
		print(ans1, ans2 % mod)
	except Exception as e:
		print(e)
t = int(input())
for _ in range(t):
	(n, m) = integer_list()
	graph = defaultdict(list)
	visited = set()
	for i in range(m):
		(a, b) = integer_list()
		graph[a].append(b)
		graph[b].append(a)
	main()


class DSU:

	def __init__(self, n):
		self.p = [-1] * n

	def find(self, n):
		if self.p[n] < 0:
			return n
		self.p[n] = self.find(self.p[n])
		return self.p[n]

	def union(self, a, b):
		a = self.find(a)
		b = self.find(b)
		if a == b:
			return
		elif self.p[a] < self.p[b]:
			self.p[a] += self.p[b]
			self.p[b] = a
		else:
			self.p[b] += self.p[a]
			self.p[a] = b

	def solution(self):
		ans = 1
		count = 0
		for el in self.p:
			if el < 0:
				count += 1
				ans = ans * abs(el) % int(1000000000.0 + 7)
		print(count, ans)
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	d = DSU(n)
	for i in range(m):
		(a, b) = map(int, input().split())
		d.union(a - 1, b - 1)
	d.solution()


from collections import defaultdict
mod = 10 ** 9 + 7
numTest = int(input())
for _ in range(numTest):
	(n, m) = map(int, input().split())
	graph = defaultdict(list)
	for _ in range(m):
		(a, b) = map(int, input().split())
		if a not in graph:
			graph[a] = []
		if b not in graph:
			graph[b] = []
		graph[a].append(b)
		graph[b].append(a)
	n_comp = 0
	comp_ways = 1
	visited = set()
	for i in range(1, n + 1):
		st = [i]
		temp = set()
		if i in visited:
			continue
		while len(st) > 0:
			curr = st.pop()
			if curr in visited:
				continue
			temp.add(curr)
			visited.add(curr)
			for j in graph[curr]:
				st.append(j)
		n_comp += 1
		comp_ways *= len(temp) % mod
	print(n_comp, comp_ways % mod)


try:
	from collections import defaultdict
	mod = 1000000007
	for _ in range(int(input())):
		(n, x) = map(int, input().split())
		d = defaultdict(list)
		for i in range(x):
			(u, v) = map(int, input().split())
			d[u].append(v)
			d[v].append(u)
		visited = [True for i in range(n + 1)]
		ans = []
		cost = 0
		for key in range(1, n + 1):
			cost = 0
			if visited[key]:
				q = [key]
				cost += 1
				visited[key] = False
				while q:
					k = q.pop(0)
					for i in d[k]:
						if visited[i]:
							visited[i] = False
							q.append(i)
							cost += 1
				ans.append(cost)
		p = 1
		for i in ans:
			p = p * i % mod
		print(len(ans), p % mod)
except:
	pass


from collections import defaultdict

class UnionFind:

	def __init__(self, n):
		self.N = n
		self.rank = [1 for i in range(0, self.N)]
		self.root = [i for i in range(0, self.N)]

	def find(self, x):
		if x == self.root[x]:
			return x
		self.root[x] = self.find(self.root[x])
		return self.root[x]

	def union(self, x, y):
		rootX = self.find(x)
		rootY = self.find(y)
		if rootX != rootY:
			if self.rank[rootX] > self.rank[rootY]:
				self.root[rootY] = rootX
			elif self.rank[rootY] > self.rank[rootX]:
				self.root[rootX] = rootY
			else:
				self.root[rootY] = rootX
				self.rank[rootX] += 1

	def connected(self, x, y):
		return self.find(x) == self.find(y)
t = int(input())
while t > 0:
	t -= 1
	(n, m) = input().split()
	(n, m) = (int(n), int(m))
	uf = UnionFind(n + 1)
	for i in range(m):
		(x, y) = input().split()
		(x, y) = (int(x), int(y))
		uf.union(x, y)
	rootdic = defaultdict(list)
	for i in range(1, n + 1):
		rootdic[uf.find(i)].append(i)
	res = 1
	for k in rootdic:
		comb = len(rootdic[k])
		res *= comb
	res = res % (10 ** 9 + 7)
	print(len(rootdic), res)


t = int(input())
while t:
	n_m = [int(item) for item in input('').split(' ')]
	n = n_m[0]
	parent = [0] * (n + 1)
	size = [0] * (n + 1)
	m = n_m[1]

	def make(v):
		parent[v] = v
		size[v] = 1
	for k in range(1, n + 1):
		make(k)

	def find(v):
		if v == parent[v]:
			return v
		parent[v] = find(parent[v])
		return parent[v]

	def union_set(i, j):
		a = find(i)
		b = find(j)
		if a != b:
			if size[a] >= size[b]:
				parent[b] = a
				size[a] = size[a] + size[b]
			else:
				parent[a] = b
				size[b] = size[b] + size[a]
	while m:
		i_j = [int(item) for item in input('').split(' ')]
		i = i_j[0]
		j = i_j[1]
		union_set(i, j)
		m = m - 1
	iterate = 1
	count = 0
	captian = 1
	while iterate <= n:
		if parent[iterate] == iterate:
			count = count + 1
			captian = captian % (10 ** 9 + 7) * (size[iterate] % (10 ** 9 + 7)) % (10 ** 9 + 7)
		iterate = iterate + 1
	print(count, captian)
	t = t - 1


import math
import sys
sys.setrecursionlimit(10000000)
p = 10 ** 9 + 7

def dfs(u, x):
	visited[u] = True
	x.add(u)
	for v in adj[u]:
		if not visited[v]:
			dfs(v, x)
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	adj = [[] for i in range(n)]
	for i in range(m):
		(u, v) = map(int, input().split())
		adj[u - 1].append(v - 1)
		adj[v - 1].append(u - 1)
	visited = [False for i in range(n)]
	components = []
	for i in range(n):
		if not visited[i]:
			x = set()
			dfs(i, x)
			components.append(len(x))
	max_esc = len(components)
	num_caps = 1
	for i in components:
		num_caps = num_caps * i % p
	print(max_esc, num_caps)


def dfs(node, graph, visited):
	visited.add(node)
	size = 0
	for neighbor in graph[node]:
		if neighbor not in visited:
			size += dfs(neighbor, graph, visited)
	return 1 + size
import sys
x = 10000000
sys.setrecursionlimit(x)
t = int(input())
for tc in range(1, t + 1):
	(n, m) = [int(i) for i in input().split(' ')]
	graph = {}
	visited = set()
	for node in range(1, n + 1):
		graph[node] = []
	for e in range(m):
		(i, j) = [int(cursor) for cursor in input().split(' ')]
		graph[i].append(j)
		graph[j].append(i)
	no_of_cc = 0
	perms = 1
	for node in graph:
		if node not in visited:
			perms = perms * dfs(node, graph, visited)
			no_of_cc += 1
	print(no_of_cc, perms % (10 ** 9 + 7))


import sys
sys.setrecursionlimit(10 ** 6)

def main():
	for _ in range(int(input())):
		(n, m) = map(int, input().split())
		parent = {k: -1 for k in range(1, n + 1)}

		def find(n):
			if parent[n] < 0:
				return n
			parent[n] = find(parent[n])
			temp = parent[n]
			return temp

		def union(a, b):
			a = find(a)
			b = find(b)
			if a == b:
				pass
			else:
				parent[b] += parent[a]
				parent[a] = b
		for _ in range(m):
			(u, v) = map(int, input().split())
			u = find(u)
			v = find(v)
			if u != v:
				union(u, v)
		captains = 1
		groups = 0
		for v in parent.values():
			if v < 0:
				groups += 1
				captains = captains * abs(v) % 1000000007
		print(groups, captains)
main()


from sys import stdin
from collections import defaultdict
mod = 10 ** 9 + 7

def bfs(c, visited, graph):
	count = 1
	visited[c] = True
	stack = [c]
	while stack:
		a = stack.pop()
		for edges in graph[a]:
			if not visited[edges]:
				count += 1
				visited[edges] = True
				stack.append(edges)
	return count
for _ in range(int(stdin.readline())):
	values = []
	some = 1
	do = 0
	(n, m) = map(int, stdin.readline().split())
	visited = [False] * (n + 1)
	graph = defaultdict(list)
	for i in range(m):
		(a, b) = map(int, stdin.readline().split())
		graph[a].append(b)
		graph[b].append(a)
	for j in range(1, n + 1):
		if not visited[j]:
			test_subject = bfs(j, visited, graph)
			do += 1
			some = some % mod * (test_subject % mod) % mod
	print(do, some)


from collections import *
t = int(input())
for k in range(t):
	(n, m) = map(int, input().split())
	susjedi = [[] for i in range(n)]
	for i in range(m):
		(a, b) = map(int, input().split())
		susjedi[a - 1].append(b - 1)
		susjedi[b - 1].append(a - 1)
	udaljenost = [-1 for i in range(n)]
	u = 1

	def bfs(x, u):
		q = deque()
		q.append(x)
		udaljenost[x] = 0
		br = 1
		while len(q) > 0:
			x = q.popleft()
			for y in susjedi[x]:
				if udaljenost[y] == -1:
					udaljenost[y] = udaljenost[x] + 1
					q.append(y)
					br = br + 1
		return [udaljenost, br]
	u = u * bfs(0, u)[1]
	komp = 1
	for i in range(n):
		if udaljenost[i] == -1:
			komp += 1
			udaljenost[i] = 0
			u = u * bfs(i, u)[1]
	print(komp, u % (10 ** 9 + 7))


from sys import stdin
input = stdin.readline
MOD = 1000 * 1000 * 1000 + 7

def dfs(start, graph, cc_size):
	stack = [start]
	while stack:
		vertex = stack.pop()
		if visited[vertex]:
			continue
		cc_size += 1
		visited[vertex] = 1
		for nodes in graph[vertex]:
			if visited[nodes] == 0:
				stack.append(nodes)
	return cc_size

def solve(graph):
	count = 0
	res = 1
	for i in range(1, len(visited)):
		cc_size = 1
		if visited[i] == 0:
			cc_size = dfs(i, graph, 0)
			count += 1
		res = res * cc_size % MOD
	print(f'{count} {res}')
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	graph = dict()
	visited = [0] * (n + 1)
	for i in range(n + 1):
		graph[i] = set()
	for i in range(m):
		(a, b) = map(int, input().split())
		graph[a].add(b)
		graph[b].add(a)
	solve(graph)


from collections import *
for t in range(int(input())):
	(n, m) = map(int, input().split())
	susjedi = defaultdict(list)
	for i in range(m):
		(a, b) = map(int, input().split())
		susjedi[a].append(b)
		susjedi[b].append(a)

	def bfs(n):
		udaljenost = [0] * (n + 1)
		brojac = 0
		for x in range(1, n + 1):
			if udaljenost[x] == 0:
				q = deque()
				q.append(x)
				udaljenost[x] = brojac + 1
				while len(q) > 0:
					x = q.popleft()
					for y in susjedi[x]:
						if udaljenost[y] == 0:
							udaljenost[y] = brojac + 1
							q.append(y)
				brojac += 1
		return udaljenost
	o = bfs(n)
	odg = Counter(o)
	nacina = 1
	for i in odg:
		if i != 0:
			nacina *= odg[i]
	print(max(o), nacina % 1000000007)


from collections import defaultdict

def find(i, fire_captains):
	if fire_captains[i] == i:
		return i
	captain = fire_captains[i]
	master_captain = find(captain, fire_captains)
	fire_captains[i] = master_captain
	return master_captain
T = int(input())
for i in range(T):
	(N, M) = (int(num) for num in input().split())
	fire_captains = [i for i in range(0, N + 1)]
	groups_size = defaultdict(int)
	for i in range(M):
		(i, j) = (int(num) for num in input().split())
		captain_i = find(i, fire_captains)
		captain_j = find(j, fire_captains)
		if captain_i < captain_j:
			fire_captains[captain_j] = captain_i
		elif captain_j < captain_i:
			fire_captains[captain_i] = captain_j
	for captain in range(1, N + 1):
		master_captain = find(captain, fire_captains)
		groups_size[master_captain] += 1
	product = 1
	for x in groups_size.values():
		product *= x
		product %= 10 ** 9 + 7
	print(len(groups_size), product)


from collections import defaultdict
visited = {}

def BFS(AList, v):
	q = [v]
	visited[v] = True
	connectedvertices = 1
	while q != []:
		j = q.pop()
		for i in AList[j]:
			if not visited[i]:
				q.append(i)
				connectedvertices += 1
				visited[i] = True
	return connectedvertices
t = int(input())
mod = 10 ** 9 + 7
for _ in range(t):
	(n, m) = map(int, input().split())
	friends = defaultdict(list)
	visited = [False] * (n + 1)
	paths = 0
	captain = 1
	for i in range(m):
		(a, b) = map(int, input().split())
		friends[a].append(b)
		friends[b].append(a)
	for i in range(1, n + 1):
		if not visited[i]:
			currentvertex = BFS(friends, i)
			paths += 1
			captain = captain % mod * (currentvertex % mod) % mod
	print(paths, captain)


from collections import defaultdict

def ConComp(graph, n):
	visited = set()
	components = []
	for i in range(1, n + 1):
		cnt = 0
		if i not in visited:
			stack = [i]
			visited.add(i)
			while stack:
				curr = stack.pop()
				cnt += 1
				for node in graph[curr]:
					if node not in visited:
						visited.add(node)
						stack.append(node)
		if cnt:
			components.append(cnt)
	leader = 1
	mod = 10 ** 9 + 7
	for i in components:
		leader *= i
	leader %= mod
	if not components:
		return [0, 0]
	return [len(components), leader]
t = int(input())
for _ in range(t):
	graph = defaultdict(list)
	(n, f) = map(int, input().split())
	for _ in range(f):
		(u, v) = map(int, input().split())
		graph[u].append(v)
		graph[v].append(u)
	ans = ConComp(graph, n)
	print(' '.join(map(str, ans)))


number_of_test_cases = int(input())

def dfs(st, graph, visited, result):
	stack = []
	stack.append(st)
	res = set()
	while len(stack) != 0:
		u = stack.pop()
		res.add(u + 1)
		if visited[u] != 1:
			visited[u] = 1
			for i in range(0, len(graph[u])):
				if visited[graph[u][i]] != 1:
					stack.append(graph[u][i])
	result *= len(res)
	return (visited, result)
for t in range(0, number_of_test_cases):
	case = input().split()
	n = int(case[0])
	r = int(case[1])
	graph = []
	for i in range(0, n):
		graph.append([])
	visited = [0] * n
	for i in range(0, r):
		(e1, e2) = map(int, input().split())
		try:
			graph[e1 - 1].append(e2 - 1)
		except:
			graph[e1 - 1] = [e2 - 1]
		try:
			graph[e2 - 1].append(e1 - 1)
		except:
			graph[e2 - 1] = [e1 - 1]
	result = 1
	g = 0
	for i in range(0, n):
		if visited[i] == 0:
			g += 1
			(visited, result) = dfs(i, graph, visited, result)
	print(g % (10 ** 9 + 7), result % (10 ** 9 + 7))


def dfs(ad, s, vis):
	st = [s]
	explo = set()
	explo.add(s)
	while st:
		v = st.pop()
		vis[v - 1] = 1
		for i in reversed(ad[v]):
			if vis[i - 1] == 0:
				st.append(i)
				explo.add(i)
	return len(explo)

def adlist(arr, n):
	ad = {}
	for i in range(n):
		ad[i + 1] = []
	for (i, j) in arr:
		ad[i].append(j)
		ad[j].append(i)
	return ad

def solve(arr, n):
	ad = adlist(arr, n)
	vis = [0] * n
	c = 0
	l = []
	for i in range(1, n + 1):
		if vis[i - 1] == 0:
			c += 1
			l.append(dfs(ad, i, vis))
	result = 1
	for i in l:
		result *= i
	q = pow(10, 9) + 7
	return (c, result % q)
for _ in range(int(input())):
	(n, e) = map(int, input().split())
	arr = []
	for i in range(e):
		arr.append(list(map(int, input().split())))
	print(*solve(arr, n))


T = int(input())
for _ in range(T):
	(n, m) = map(int, input().split())
	adj = {}
	for i in range(m):
		(e1, e2) = map(int, input().split())
		try:
			adj[e1].append(e2)
		except:
			adj[e1] = [e2]
		try:
			adj[e2].append(e1)
		except:
			adj[e2] = [e1]
	routes = []
	visited = {i: False for i in range(1, n + 1)}
	for i in range(1, n + 1):
		if not visited[i]:
			visited[i] = True
			q = [i]
			routes.append([i])
			while len(q) > 0:
				curr = q.pop(0)
				adj_curr = adj.get(curr, [])
				for node in adj_curr:
					if not visited[node]:
						q.append(node)
						visited[node] = True
						routes[-1].append(node)
	count = 1
	for route in routes:
		count = count * len(route)
	print(len(routes) % (10 ** 9 + 7), count % (10 ** 9 + 7))


def checker(graph, node):
	if graph[node] < 0:
		return node
	else:
		temp = checker(graph, graph[node])
		graph[node] = temp
		return temp

def union(graph, u, v):
	u = checker(graph, u)
	v = checker(graph, v)
	if graph[u] <= graph[v]:
		graph[u] = graph[u] + graph[v]
		graph[v] = u
	else:
		graph[v] = graph[v] + graph[u]
		graph[u] = v
for _ in range(int(input())):
	(n, e) = map(int, input().split())
	graph = [-1] * (n + 1)
	for _ in range(e):
		(u, v) = map(int, input().split())
		if checker(graph, u) != checker(graph, v):
			union(graph, u, v)
	count = 0
	mul = 1
	mod = 10 ** 9 + 7
	for item in graph[1:]:
		if item < 0:
			count += 1
			mul = mul % mod * (-item % mod) % mod
	print(count, mul)


mod = 10 ** 9 + 7
t = int(input())

def find(x, parents):
	if parents[x] == x:
		return x
	parents[x] = find(parents[x], parents)
	return parents[x]
while t:
	(N, M) = map(int, input().split())
	parents = [i for i in range(N + 1)]
	rank = [1 for i in range(N + 1)]
	while M:
		(a, b) = map(int, input().split())
		pa = find(a, parents)
		pb = find(b, parents)
		if pa != pb:
			if rank[pa] > rank[pb]:
				parents[pb] = pa
				rank[pa] += rank[pb]
			else:
				parents[pa] = pb
				rank[pb] += rank[pa]
		M -= 1
	a = 1
	cnt = 0
	for i in range(1, len(parents)):
		if parents[i] == i:
			cnt += 1
			a = a * rank[i] % mod
	print(cnt, a)
	t -= 1


import sys

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def get_list():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_string():
	return sys.stdin.readline().strip()

def get_int():
	return int(sys.stdin.readline().strip())

def get_list_strings():
	return list(map(str, sys.stdin.readline().strip().split()))

def solve(N, M, arr):
	store = {}
	for ele in arr:
		node1 = ele[0]
		node2 = ele[1]
		if node1 not in store:
			store[node1] = [node2]
		else:
			store[node1].append(node2)
		if node2 not in store:
			store[node2] = [node1]
		else:
			store[node2].append(node1)
	for i in range(1, N + 1):
		if i in store:
			continue
		store[i] = []
	count = 0
	present = {}
	req = []
	for node in range(1, N + 1):
		if node in present:
			continue
		count += 1
		temp = 0
		queue = [node]
		while queue:
			current = queue.pop()
			if current in present:
				continue
			present[current] = 1
			temp += 1
			for ele in store[current]:
				if ele not in present:
					queue.append(ele)
		req.append(temp)
	ways = 1
	for ele in req:
		ways *= ele
		ways = ways % (10 ** 9 + 7)
	res = [count, ways]
	sys.stdout.write(' '.join(map(str, res)) + '\n')
T = get_int()
while T:
	(N, M) = get_ints()
	arr = []
	tempM = M
	while tempM:
		(i, j) = get_ints()
		arr.append([i, j])
		tempM -= 1
	solve(N, M, arr)
	T -= 1


import sys
from os import path
sys.setrecursionlimit(10 ** 6)
mod = 10 ** 9 + 7
if path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
test = int(sys.stdin.readline().rstrip())
while test > 0:
	test -= 1
	(n, m) = map(int, sys.stdin.readline().rstrip().split())
	a = []
	g = [[] * 1 for i in range(n + 1)]
	for x in range(m):
		b = list(map(int, sys.stdin.readline().rstrip().split()))
		a.append(b)
	for x in range(m):
		g[a[x][0]].append(a[x][1])
		g[a[x][1]].append(a[x][0])
	visited = [False] * (n + 1)
	visited[0] = True
	c = 0
	global c1
	ans = 1

	def dfs(v):
		global c1
		visited[v] = True
		c1 += 1
		for x in range(len(g[v])):
			child = g[v][x]
			if not visited[child]:
				dfs(child)
	for x in range(1, n + 1):
		if not visited[x]:
			c1 = 0
			c += 1
			dfs(x)
			ans = ans * c1 % mod
	print(c, ans % mod)


lim = 10 ** 9 + 7

def bfs(adj, start, already):
	que = [start]
	count = 0
	first = 0
	last = 1
	while first < last:
		element = que.pop(0)
		already[element] = False
		count += 1
		possible = adj[element]
		for i in possible:
			if already.get(i, True):
				que.append(i)
				last += 1
				already[i] = False
		first += 1
	return (count, already)
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	adj = {}
	for i in range(1, n + 1):
		adj[i] = []
	for i in range(m):
		(x, y) = map(int, input().split())
		adj[x].append(y)
		adj[y].append(x)
	already = {}
	total_cap = 1
	total_route = 0
	for i in range(1, n + 1):
		if already.get(i, True):
			total_route += 1
			(count, already) = bfs(adj, i, already)
			total_cap = total_cap * count
	print(total_route, int(total_cap % lim))


def dps(i):
	count = 0
	stack = [i]
	while len(stack) > 0:
		k = stack.pop()
		if not p[k]:
			count += 1
			p[k] = True
			for q in l[k]:
				if not p[q]:
					stack.append(q)
	return count
t = int(input())
lr = []
lc = []
u = 10 ** 9 + 7
for t2 in range(0, t):
	(r, c) = (0, 1)
	(n, m) = map(int, input().split())
	l = [[] for i in range(0, n)]
	p = [False for i in range(0, n)]
	for i in range(0, m):
		(p1, p2) = map(int, input().split())
		l[p1 - 1].append(p2 - 1)
		l[p2 - 1].append(p1 - 1)
	for i in range(0, n):
		if not p[i]:
			a = dps(i)
			r += 1
			c = c * (a % u) % u
	lr.append(r)
	lc.append(c)
for i in range(0, t):
	print(lr[i], lc[i])


import sys
sys.setrecursionlimit(210000)
from collections import defaultdict
t = int(input())
for k in range(t):
	(n, m) = map(int, input().split())
	d = defaultdict(list)
	visit = [0] * 200001
	c = 0
	res = 1
	global cnt
	for i in range(m):
		(a, b) = map(int, input().split())
		d[a].append(b)
		d[b].append(a)

	def dfs(node, cnt):
		visit[node] = 1
		cnt += 1
		for j in d[node]:
			if visit[j] == 0:
				cnt = dfs(j, cnt)
		return cnt
	for i in range(1, n + 1):
		if visit[i] == 0:
			cnt = 0
			v = dfs(i, cnt)
			c += 1
			res = res * v % (10 ** 9 + 7)
	print(c, res)


def sol(n, emp):
	(groups, vis, poscom) = ([], {}, 1)
	for s in range(1, n + 1):
		if not vis.get(s, 1):
			continue
		(sta, friends) = ([s], [s])
		vis[s] = None
		while sta:
			s = sta.pop(-1)
			for f in emp[s]:
				if vis.get(f, 1):
					sta.append(f)
					friends.append(f)
					vis[f] = None
		poscom *= len(friends)
		poscom %= int(1000000000.0 + 7)
		groups.append(friends)
	return str(len(groups)) + ' ' + str(poscom)
for _ in range(int(input())):
	(no_emp, ip) = map(int, input().split())
	emp = {i: [] for i in range(1, no_emp + 1)}
	for _ in range(ip):
		(a, b) = map(int, input().split())
		emp[a].append(b)
		emp[b].append(a)
	print(sol(no_emp, emp))


import sys

def dfs(rt):
	if not vis[rt]:
		vis[rt] = True
		nodCount = 1
		for node in graph[rt]:
			nodCount += dfs(node)
		return nodCount
	return 0
sys.setrecursionlimit(10 ** 6)
R = lambda : list(map(int, input().split()))
for _ in range(int(input())):
	(n, m) = R()
	graph = [[] for i in range(n + 1)]
	vis = [False for i in range(n + 1)]
	for i in range(m):
		(u, v) = R()
		graph[u].append(v)
		graph[v].append(u)
	res = []
	for i in range(1, n + 1):
		t = dfs(i)
		if t:
			res.append(t)
	MOD = 1000000007
	(a, b) = (len(res), 1)
	for i in range(len(res)):
		b = b * res[i] % MOD
	print(a, b)


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
from collections import defaultdict
testcases = int(input())
for case in range(testcases):

	class Graph:

		def __init__(self):
			self.graph = defaultdict(list)

		def addEdge(self, u, v):
			self.graph[u].append(v)
	(n, e) = [int(i) for i in input().split()]
	g = Graph()
	for i in range(e):
		(u, v) = [int(i) for i in input().split()]
		g.addEdge(u, v)
		g.addEdge(v, u)
	visited = set()
	dic = defaultdict(list)

	def DFS(i, dic):
		dic.append(i)
		visited.add(i)
		for neighbor in g.graph[i]:
			if neighbor not in visited:
				DFS(neighbor, dic)
	for i in range(1, n + 1):
		if i not in visited:
			DFS(i, dic[i])
	capt = 1
	for i in dic:
		capt *= len(dic[i])
	print(len(dic), capt % (10 ** 9 + 7))


import sys

def depth_first_search(x, tree, visited):
	size = 1
	stack = [x]
	visited[x] = 1
	while stack:
		top = stack.pop()
		for i in tree[top]:
			if not visited[i]:
				visited[i] = 1
				size += 1
				stack.append(i)
	return size
t = int(input())
while t:
	t -= 1
	(n, m) = map(int, sys.stdin.readline().strip().split())
	tree = {i: [] for i in range(n + 1)}
	visited = [0] * (n + 1)
	while m:
		m -= 1
		(i, j) = map(int, sys.stdin.readline().strip().split())
		tree[i].append(j)
		tree[j].append(i)
	m = 10 ** 9 + 7
	ways = 1
	count = 0
	for k in range(1, n + 1):
		if not visited[k]:
			a = depth_first_search(k, tree, visited)
			ways *= a
			ways %= m
			count += 1
	print(count, ways)


import sys
sys.setrecursionlimit(int(1000000.0))

def dfs(ver):
	cnt = 0
	vis.add(ver)
	for neigh in graph[ver]:
		if neigh not in vis:
			cnt += dfs(neigh)
	return (cnt + 1) % (int(1000000000.0) + 7)
for t in range(int(input())):
	(v, e) = map(int, input().split())
	from collections import defaultdict
	graph = defaultdict(list)
	for i in range(e):
		(v1, v2) = map(int, input().split())
		graph[v1].append(v2)
		graph[v2].append(v1)
	vis = set()
	mod = int(1000000000.0) + 7
	cnt = 0
	ans = 1
	for i in range(1, v + 1):
		if i not in vis:
			cnt += 1
			ans = ans * (dfs(i) % mod) % mod
	print(cnt, ans)


from sys import stdin, stdout
from math import gcd, sqrt, floor, ceil
from collections import defaultdict
input = stdin.readline

def list_inp(x):
	return list(map(x, input().split()))

def map_inp(x):
	return map(x, input().split())

def lcm(a, b):
	return a * b / gcd(a, b)

def add(u, v):
	d[u].append(v)
	d[v].append(u)

def dfs(s, vis, cnt):
	qq = []
	qq.append(s)
	while qq:
		x = qq.pop()
		cnt[0] += 1
		for i in d[x]:
			if vis[i] != 1:
				vis[i] = 1
				qq.append(i)
	return
mod = int(10 ** 9) + 7
t = int(input())
for _ in range(t):
	d = defaultdict(list)
	(n, m) = map_inp(int)
	vis = [0] * (n + 1)
	nofe = 1
	for i in range(m):
		(u, v) = map_inp(int)
		add(u, v)
	gcnt = 0
	for i in range(1, n + 1):
		if vis[i] == 1:
			continue
		cnt = [0]
		gcnt += 1
		vis[i] = 1
		dfs(i, vis, cnt)
		nofe *= cnt[0]
	print(gcnt, nofe % mod)


from collections import defaultdict, deque
t = int(input())

def dfs(node, vis, adjlist, no_of_nodes):
	vis[node] = 1
	no_of_nodes += 1
	for adj in adjlist[node]:
		if vis[adj] == 0:
			no_of_nodes = max(no_of_nodes, dfs(adj, vis, adjlist, no_of_nodes))
	return no_of_nodes

def bfs(node, vis, adjlist):
	vis[node] = 1
	q = deque()
	q.append(node)
	no_of_nodes = 0
	while q:
		cur = q.popleft()
		no_of_nodes += 1
		for adj in adjlist[cur]:
			if vis[adj] == 0:
				vis[adj] = 1
				q.append(adj)
	return no_of_nodes
for t1 in range(t):
	(n, e) = [int(x) for x in input().split()]
	adjlist = defaultdict(list)
	for i in range(e):
		(u, v) = [int(x) for x in input().split()]
		adjlist[u - 1].append(v - 1)
		adjlist[v - 1].append(u - 1)
	c = 0
	mul = 1
	vis = [0] * n
	for i in range(n):
		if vis[i] == 0:
			mul = mul * bfs(i, vis, adjlist)
			c += 1
	print(c, end=' ')
	print(mul % (pow(10, 9) + 7))


import sys
sys.setrecursionlimit(100000000)

def dfs(u, m):
	visited[u] = True
	routes[m] = routes[m] + 1
	for i in graph[u]:
		if visited[i] != True:
			dfs(i, m)
M = 1000000007
for _ in range(0, int(input())):
	routes = {}
	elements = []
	graph = {}
	visited = {}
	(n, m) = map(int, input().split())
	for i in range(1, n + 1):
		elements.append(i)
		routes[i] = 0
		graph[i] = []
		visited[i] = False
	for _ in range(0, m):
		(i, j) = map(int, input().split())
		graph[i].append(j)
		graph[j].append(i)
	for i in elements:
		if visited[i] == False:
			dfs(i, i)
	cum_pro = 1
	co = 0
	for i in routes.keys():
		if routes[i] != 0:
			co = co + 1
			cum_pro = cum_pro * routes[i] % M
	print(co, cum_pro)


import sys
sys.setrecursionlimit(100000000)

def visit(li, i, vis):
	vis[i] = True
	ans = 1
	for j in li[i]:
		if not vis[j]:
			ans += visit(li, j, vis)
	return ans
t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	li = [[] for i in range(n + 1)]
	vis = [False] * (n + 1)
	vis[0] = True
	for i in range(m):
		(x, y) = map(int, input().split())
		li[x].append(y)
		li[y].append(x)
	(ans, fesc) = (1, 0)
	for i in range(n + 1):
		if not vis[i]:
			ans = ans * visit(li, i, vis)
			fesc += 1
	print(fesc, ans % 1000000007)