Read problem statements in [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

You are given a graph $G$ with $N$ vertices (numbered $1$ through $N$) and $M$ edges. You should partition the vertices of $G$ into two sets $A$ and $B$ such that:
each vertex of $G$ belongs to exactly one of these sets
$A$ is non-empty
$A$ is an independent set in $G$, i.e. for each pair of vertices $u, v \in A$, $G$ does not contain an edge $(u, v)$
for each vertex $a \in A$ and each vertex $b \in B$, there is an edge $(a, b)$ in $G$

Find the number of such partitions $(A, B)$. Also, give an example of one of these partitions or determine that no such partition exists.

Two partitions are considered different if there is a vertex that is in the set $A$ in one partition and in the set $B$ in the other partition.

------  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$.
Each of the next $M$ lines contains two space-separated integers $u$ and $v$ denoting that vertices $u$ and $v$ are connected by an edge.

------  Output ------
For each test case, print two lines.
The first of these lines should contain a single integer — the number of partitions satisfying the given conditions.
The second line should contain a single string with length $N$. If there are no partitions satisfying the given conditions, each character of this string should be '0'. Otherwise, this string should describe one such partition — for each valid $i$, the $i$-th character should be '1' if vertex $i$ belongs to $A$ or '0' if it belongs to $B$.

------  Constraints  ------
$1 ≤ T ≤ 5 \cdot 10^{5}$
$1 ≤ N, M ≤ 5 \cdot 10^{5}$
$1 ≤ u, v ≤ N$
there are no self-loops or duplicate edges in the graph
the sum of $N$ over all test cases does not exceed $5 \cdot 10^{5}$
the sum of $M$ over all test cases does not exceed $5 \cdot 10^{5}$

------  Subtasks ------
Subtask #1 (30 points): $N,M,T ≤ 100$

Subtask #2 (70 points): original constraints

----- Sample Input 1 ------ 
1

5 7

1 3

1 4

1 5

2 3

2 4

2 5

3 4
----- Sample Output 1 ------ 
1

11000
----- explanation 1 ------ 
Example case 1: The only possible partition satisfying the given conditions is $A = \{1, 2\}, B = \{3, 4, 5\}$.

Source: codechef | Difficulty: VERY_HARD
Tags: Graph algorithms

Constructive algorithms


Solutions:
lii = lambda x: list(map(x, input().split()))
iip = lambda : int(input())
from fractions import Fraction
from collections import defaultdict, deque

def solve():
	(n, m) = lii(int)
	graph = defaultdict(list)
	for i in range(m):
		(u, v) = lii(int)
		graph[u].append(v)
		graph[v].append(u)
	seta = defaultdict(list)
	for i in graph.keys():
		seta[frozenset(graph[i])].append(i)
	ss = [0] * n
	sets = 0
	for i in seta.keys():
		if len(i) + len(seta[i]) == n:
			if sets == 0:
				for i in seta[i]:
					ss[i - 1] = 1
			sets += 1
	print(sets)
	print(*ss, sep='')
tc = 1
tc = iip()
for _ in range(tc):
	solve()


from sys import stdin

def input():
	return stdin.readline()

def solve():
	for i in range(1, n + 1):
		if not links[i]:
			print(0)
			print('0' * n)
			return
	visited = set()
	partitions = 0
	output = ''
	for i in range(1, n + 1):
		if i in visited:
			continue
		missing_links = set()
		for k in range(1, n + 1):
			if k not in links[i]:
				missing_links.add(k)
		for j in missing_links:
			if links[j] != links[i]:
				break
		else:
			partitions += 1
			if not output:
				for k in range(1, n + 1):
					if k in missing_links:
						output += '1'
					else:
						output += '0'
		visited |= missing_links
	print(partitions)
	if output:
		print(output)
	else:
		print('0' * n)
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	links = [set() for i in range(n + 1)]
	for i in range(m):
		(u, v) = map(int, input().split())
		links[u].add(v)
		links[v].add(u)
	solve()


def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a

def prime(n):
	arr = [True] * (n + 1)
	arr[0] = False
	arr[1] = False
	for i in range(n + 1):
		if arr[i]:
			for j in range(i * i, n + 1, i):
				arr[j] = False
	return arr[n]
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	graph = [[] for i in range(n + 1)]
	for _ in range(m):
		(i, j) = map(int, input().split())
		graph[i].append(j)
		graph[j].append(i)
	count = 0
	seen = {}
	for i in range(1, n + 1):
		t = tuple(sorted(graph[i]))
		if t not in seen:
			seen[t] = []
		seen[t].append(i)
	ans = ['0' for _ in range(n)]
	for t in seen:
		if n == len(t) + len(seen[t]):
			count += 1
			if count == 1:
				for i in range(1, n + 1):
					if i in seen[t]:
						ans[i - 1] = '1'
	print(count)
	print(''.join(ans))


from sys import stdin, stdout
input = stdin.readline
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	graph = [[] for i in range(n + 1)]
	for i in range(m):
		(a, b) = map(int, input().split())
		graph[a].append(b)
		graph[b].append(a)
	hash = {}
	for i in range(1, n + 1):
		adj = tuple(sorted(graph[i]))
		if adj not in hash:
			hash[adj] = []
		hash[adj].append(i)
	count = 0
	ans = [str(0) for i in range(n)]
	for i in hash:
		if len(i) + len(hash[i]) == n:
			count += 1
			if count == 1:
				for j in hash[i]:
					ans[j - 1] = str(1)
	print(count)
	print(''.join(ans))


import sys
input = sys.stdin.readline

def solution(N, M, edges):
	set_verts_tried = set()
	adj = [set() for _ in range(N)]
	comp_a = set()
	full_set = set(list(range(N)))
	count_poss = 0
	sol_B = set()
	for [u, v] in edges:
		adj[u - 1].add(v - 1)
		adj[v - 1].add(u - 1)
	for a in range(N):
		if a not in set_verts_tried:
			set_verts_tried.add(a)
			comp_a = full_set - adj[a] - set([a])
			possible_a = True
			for pot_a in comp_a:
				if pot_a in set_verts_tried or len(adj[a]) != len(adj[pot_a]) or adj[a] != adj[pot_a]:
					possible_a = False
					break
			if possible_a:
				if count_poss == 0:
					sol_B = adj[a]
				count_poss += 1
			for pot_a in comp_a:
				set_verts_tried.add(pot_a)
	print(count_poss)
	if count_poss == 0:
		seq = [str(0) for _ in range(N)]
	else:
		seq = [str(0) if elem in sol_B else str(1) for elem in range(N)]
	print(''.join(seq))
for _ in range(int(input())):
	(N, M) = map(int, input().split())
	edges = [list(map(int, input().split())) for _ in range(M)]
	solution(N, M, edges)