Ratan Singh and Alauddin Khilji are blood-enemies of each other. Ratan Singh has a diverse and well planned kingdom. His kingdom has N provinces. Every province has a  bidirectional road to every other province (except itself of course). But Alauddin has now attacked his kingdom. During his attack, he destroyed some of the roads connecting provinces.

To fight back, Ratan Singh divided his sena(army) into two senas. Sena X and Sena Y.
Sena X has the best warriors, while Sena Y doesn’t. According to his plan, each province should be protected by exactly one of the two senas( X or Y).

As Sena X is very strong, Ratan Singh will place them in such a way that: 
- No two adjacent provinces (provinces connected by a road) are guarded by Sena X. 
- If a province P is guarded by Sena X, then all the provinces which are guarded by Sena Y needs to be adjacent to province P. 
- There should exist at least one province having Sena X, and at least one province having Sena Y.

This way, he can ensure the safety of his Kingdom.
 
You are the only programmer that Khilji has. You have to help him calculate the number of possible ways in which Ratan Singh can achieve the aforementioned task!

NOTE : Please use Fast I/O methods as the input can be large.

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

- First line will contain T, number of testcases. Then the testcases follow.
- First line of each test-case consists of two spaced integers, N and M, denoting the number of provinces in Ratan Singh's Kingdom, and the number of roads destroyed by Khilji respectively.
- Then, M lines follow:
- Each of these lines consists of two spaced integers, u v, denoting that the road connecting provinces u and v has been destroyed by Khilji. 

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

For each testcase, print the number of possible ways in which Ratan Singh can deploy his Senas, following the conditions mentioned in the statement.

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

$1 ≤ T ≤ 10^{5}$
$2 ≤ N ≤ 2 \cdot 10^{5}$
$0 ≤ M ≤ min( \frac{N \cdot (N-1)}{2},3 \cdot 10^{5})$
$u \neq v$.
- All the edges mentioned in the input are unique.
- The sum of $N$ over all cases doesn't exceed $2 \cdot 10^{5}$
- The sum of $M$ over all cases doesn't exceed $5 \cdot 10^{5}$.

----- Sample Input 1 ------ 
1
6 5
1 6
2 4
2 5
3 5
4 5

----- Sample Output 1 ------ 
1

----- explanation 1 ------ 
- The only possible way to deploy the senas is, deploy the Sena $X$ at provinces :$[1,6]$ and the ena $Y$ at provinces : $[3,2,4,5]$. For any of the provinces having Sena $X$, it can be seen that, every province of sena $Y$ is adjacent to it. Province $1$ is adjacent to $[3,2,4,5]$, the same follows for the province $6$.
 
- He cannot deploy sena $X$ at $[3,2,4,5]$ and $Y$ at $[1,6]$ because in the resulting graph, provinces $3,2$ as well as provinces $3,4$ are adjacent.

Source: codechef | Difficulty: VERY_HARD
Tags: Data structures

Graph algorithms

Graph traversal


Solutions:
from collections import defaultdict as dd
from sys import stdin, stdout, setrecursionlimit
(readline, writeline) = (stdin.readline, stdout.write)
setrecursionlimit(100005)

def dfs(x, visited, lst):
	lst.append(x)
	visited.add(x)
	for i in graph[x]:
		if i not in visited:
			dfs(i, visited, lst)
for _ in range(int(readline())):
	(n, m) = map(int, readline().split())
	deg = [0] * (n + 1)
	graph = dd(list)
	for i in range(m):
		(u, v) = map(int, readline().split())
		graph[u].append(v)
		graph[v].append(u)
		deg[u] += 1
		deg[v] += 1
	visited = set()
	(ans, cnt) = (0, 0)
	for i in range(1, n + 1):
		if i not in visited:
			lst = []
			dfs(i, visited, lst)
			visited.add(i)
			l = len(lst)
			flag = 1
			for j in lst:
				if deg[j] != l - 1:
					flag = 0
					break
			if flag:
				ans += 1
			cnt += 1
	if cnt == 1:
		ans = 0
	print(ans)


import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

def dfs(ver, comp):
	vis[ver] = True
	comp.append(ver)
	for ngh in adj[ver]:
		if not vis[ngh]:
			dfs(ngh, comp)
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	adj = [[] for _ in range(n + 1)]
	for _ in range(m):
		(u, v) = map(int, input().split())
		adj[u].append(v)
		adj[v].append(u)
	vis = [False] * (n + 1)
	aux = []
	for i in range(1, n + 1):
		if not vis[i]:
			c = []
			dfs(i, c)
			aux.append(c)
	ans = 0
	for com in aux:
		ne = 0
		for i in com:
			ne += len(adj[i])
		if ne == len(com) * (len(com) - 1):
			ans += 1
	if m == n * (n - 1) // 2:
		ans = 0
	print(ans)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	graph = [[i] for i in range(n + 1)]
	for _ in range(m):
		(u, v) = map(int, input().split())
		graph[u].append(v)
		graph[v].append(u)
	mp = {}
	for item in graph:
		mp[tuple(sorted(item))] = 0
	for item in graph:
		mp[tuple(sorted(item))] += 1
	cnt = 0
	for item in mp:
		if mp[item] == len(item) and len(item) != n:
			cnt += 1
	print(cnt - 1)


import sys
input = sys.stdin.readline
from collections import defaultdict

def Union(a, b):
	founder_a = Find(a)
	founder_b = Find(b)
	if founder_a == founder_b:
		num_edges_in_group[founder_a] += 1
		return
	founder[founder_b] = founder_a
	num_nodes_in_group[founder_a] += num_nodes_in_group[founder_b]
	num_edges_in_group[founder_a] += num_edges_in_group[founder_b] + 1
	return

def Find(node):
	if founder[node] == node:
		return node
	founder[node] = Find(founder[node])
	return founder[node]
num_test_cases = int(input())
for _ in range(num_test_cases):
	(num_nodes, num_destroyed_edges) = [int(x) for x in input().split()]
	founder = {n: n for n in range(1, num_nodes + 1)}
	num_nodes_in_group = defaultdict(lambda : 1)
	num_edges_in_group = defaultdict(int)
	for i in range(num_destroyed_edges):
		(u, v) = [int(x) for x in input().split()]
		Union(u, v)
	ans = 0
	founders = {Find(node) for node in range(1, num_nodes + 1)}
	for n in founders:
		if num_nodes_in_group[n] < num_nodes and num_edges_in_group[n] == num_nodes_in_group[n] * (num_nodes_in_group[n] - 1) // 2:
			ans += 1
	print(ans)


import sys
import math
import bisect
from sys import stdin, stdout
from math import gcd, floor, sqrt, log
from collections import defaultdict as dd
from bisect import bisect_left as bl, bisect_right as br
from collections import Counter
from collections import defaultdict as dd
sys.setrecursionlimit(100000)
flush = lambda : stdout.flush()
stdstr = lambda : stdin.readline()
stdint = lambda : int(stdin.readline())
stdpr = lambda x: stdout.write(str(x))
stdmap = lambda : map(int, stdstr().split())
stdarr = lambda : list(map(int, stdstr().split()))
mod = 1000000007

def DFS(node, graph, comp, visited):
	visited[node] = True
	comp.append(node)
	for i in graph[node]:
		if not visited[i]:
			DFS(i, graph, comp, visited)
for _ in range(stdint()):
	(n, m) = stdmap()
	if m == 0:
		print(n)
		continue
	graph = dd(list)
	deg = Counter()
	for i in range(m):
		(a, b) = stdmap()
		graph[a].append(b)
		graph[b].append(a)
		deg[a] += 1
		deg[b] += 1
	comps = []
	visited = [False] * (n + 1)
	for i in range(1, n + 1):
		if not visited[i]:
			comp = []
			DFS(i, graph, comp, visited)
			comps.append(comp)
	res = 0
	for i in comps:
		pos = True
		for j in i:
			if deg[j] != len(i) - 1:
				pos = False
				break
		if pos:
			res += 1
	if len(comps) == 1 and res == 1:
		res -= 1
	print(res)


import sys

def get_int():
	return map(int, sys.stdin.readline().strip().split())
T = int(input())
for i in range(T):
	yesval = 'yes'
	total = 0
	(N, M) = get_int()
	graphc = [[] for kappa in range(N)]
	for theta in range(M):
		(u, v) = get_int()
		graphc[u - 1].append(v - 1)
		graphc[v - 1].append(u - 1)
	for alpha in range(N):
		if len(graphc[alpha]) == N - 1:
			yesval = 'no'
		graphc[alpha].sort()
	marked = [False for delta in range(N)]
	counter = 0
	while counter < N:
		if marked[counter]:
			counter += 1
		else:
			temp_arr = graphc[counter]
			marked[counter] = True
			for beta in temp_arr:
				marked[beta] = True
			l = len(temp_arr)
			works = 'yes'
			for gamma in range(l):
				val = temp_arr[gamma]
				del temp_arr[gamma]
				del graphc[val][0]
				if temp_arr != graphc[val]:
					works = 'no'
				graphc[val].insert(0, counter)
				temp_arr.insert(gamma, val)
			if works == 'yes':
				total += 1
	if yesval == 'no':
		sys.stdout.write(str(0) + '\n')
	else:
		sys.stdout.write(str(total) + '\n')


from sys import stdin
input = stdin.readline

def answer():
	v = [False] * (n + 1)
	ans = 0
	for i in range(1, n + 1):
		if v[i]:
			continue
		v[i] = True
		add = 1
		for j in adj[i]:
			if len(adj[j]) != len(adj[i]):
				add = 0
			count = 0
			for k in adj[j]:
				if k not in adj[i]:
					count += 1
			if count > 1:
				add = 0
			v[j] = True
		ans += add
	return ans
for T in range(int(input())):
	(n, m) = map(int, input().split())
	if m == 0:
		print(n)
		continue
	adj = [set() for i in range(n + 1)]
	for i in range(m):
		(u, v) = map(int, input().split())
		adj[u].add(v)
		adj[v].add(u)
	d = dict()
	for i in range(1, n + 1):
		x = tuple(sorted(list(adj[i])))
		d[x] = d.get(x, 0) + 1
	yes = True
	for x in d.keys():
		if len(x) + d[x] == n:
			yes = False
			break
	if yes == False:
		print(0)
	else:
		print(answer())


def solve():
	(n, m) = inl()
	arr = [[i] for i in range(n + 1)]
	for i in range(m):
		(u, v) = inl()
		arr[u].append(v)
		arr[v].append(u)
	mp = {}
	for item in arr:
		mp[tuple(sorted(item))] = 0
	for item in arr:
		mp[tuple(sorted(item))] += 1
	cnt = 0
	for item in mp:
		if mp[item] == len(item) and len(item) != n:
			cnt += 1
	print(cnt - 1)

def inl():
	return [int(i) for i in input().split()]

def inp():
	return int(input())
t = 1
t = inp()
while t:
	solve()
	t -= 1


import sys

def is_complete(src):
	for node in g[src]:
		v[node] = True
	for i in g[src]:
		if len(g[i]) != len(g[src]):
			return False
		for j in g[src]:
			if i not in g[j]:
				return False
	return True
for test in range(int(input())):
	(n, m) = map(int, sys.stdin.readline().split())
	g = [{i} for i in range(n + 1)]
	for _ in range(m):
		(u, v) = map(int, sys.stdin.readline().split())
		g[u].add(v)
		g[v].add(u)
	if m == n * (n - 1) // 2:
		print(0)
		continue
	cnt = 0
	v = [False] * (n + 1)
	for i in range(1, n + 1):
		if not v[i]:
			if is_complete(i):
				cnt += 1
	print(cnt)