This is the easy version of the problem. The only difference between the easy and hard versions is that, in the easy one, additionally, there exists a solution with at least 2 employees in every department.

ChefCorp has N employees. Each employee belongs to exactly one of the M departments. Each department is headed by exactly one of the employees belonging to that department.

The management structure of ChefCorp is as follows:
Each employee of a department (including its head) is *in contact* with every other employee of that department.
The head of each department is *in contact* with the heads of all the other departments.

For example, let N = 7, M = 3 and employees 1, \textbf{2}, 3 belong to the first department, employees \textbf{4}, 5 belong to the second department and employees \textbf{6}, 7 belong to the third department (employees in bold represent the heads of the departments). The following pairs of employees are in contact with each other: (1, 2), (1, 3), (2, 3), (4, 5), (6, 7), (2, 4), (4, 6), (2, 6).

However, due to some inexplicable reasons, ChefCorp loses all its data on the departments. Given the total number of employees N and every pair of employees who are *in contact* with each other, can you help recover the number of departments and the employees belonging to each of the departments?

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

- The first line contains a single integer T — the number of test cases. Then the test cases follow.
- The first line of each test case contains a single integer N — the total number of employees in ChefCorp.
- The second line of each test case contains a single integer K — the number of pairs of employees *in contact* with each other.
- K lines follow. The i^{th} of these K lines contain two space-separated integers u_{i} and v_{i}, denoting that employee u_{i} is *in contact* with v_{i}.

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

- For each test case, output the following:
- In the first line output M — the number of departments.
- In the second line, output N space-separated integers D_{1}, D_{2}, \ldots, D_{N} (1 ≤ D_{i} ≤ M) — denoting that the i^{th} employee belongs to the D_{i}^{th} department.
- In the third line, output M space-separated integers H_{1}, H_{2}, \ldots, H_{M} (1 ≤ H_{i} ≤ N, H_{i} \neq H_{j} when i \neq j) — denoting that the H_{i}^{th} employee is the head of the i^{th} department.

If there are multiple answers, output any. It is guaranteed that at least one solution always exists.

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

$1 ≤ T ≤ 1000$
$2 ≤ N ≤ 1000$
$1 ≤ K ≤ \frac{N\cdot(N-1)}{2}$
$1 ≤ u_{i}, v_{i} ≤ N$
$u_{i} \neq v_{i}$ for each $1 ≤ i ≤ K$.
- It is guaranteed that there exists a solution in which there are at least two employees in every department.
- The sum of $N$ over all test cases does not exceed $3000$.

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

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

----- explanation 1 ------ 
Test Case $1$: Explained in the problem statement.

Source: codechef | Difficulty: VERY_HARD
Tags: Graph algorithms

Data structures


Solutions:
import heapq
import math

def get_distances(adjacencies, root):
	min_dist = len(adjacencies) * [math.inf]
	to_visit = [(0, root)]
	while len(to_visit) != 0:
		(dist, i) = heapq.heappop(to_visit)
		if dist < min_dist[i]:
			assert min_dist[i] == math.inf
			min_dist[i] = dist
			for new_i in adjacencies[i]:
				heapq.heappush(to_visit, (dist + 1, new_i))
	return min_dist
t = int(input())
for _ in range(t):
	n = int(input())
	adjacencies = []
	for i in range(n):
		adjacencies.append([])
	k = int(input())
	for __ in range(k):
		(u, v) = (int(x) for x in input().split())
		adjacencies[u - 1].append(v - 1)
		adjacencies[v - 1].append(u - 1)
	dists_0 = get_distances(adjacencies, 0)
	max_dist = max(dists_0)
	if max_dist == 1:
		print(1)
		print('1 ' * n)
		print(1)
		continue
	assert max_dist >= 2 and max_dist <= 3
	assigned_department = n * [None]
	num_depts = 0
	for i in range(n):
		if dists_0[i] == max_dist and assigned_department[i] is None:
			assigned_department[i] = num_depts
			for j in adjacencies[i]:
				assigned_department[j] = num_depts
			num_depts += 1
	for i in range(n):
		if assigned_department[i] is None:
			assigned_department[i] = num_depts
	num_depts += 1
	heads = num_depts * [None]
	for i in range(n):
		if any((assigned_department[j] != assigned_department[i] for j in adjacencies[i])):
			heads[assigned_department[i]] = i
	print(num_depts)
	for x in assigned_department:
		print(x + 1, end=' ')
	print()
	for x in heads:
		print(x + 1, end=' ')
	print()


t = int(input())

def Intersection(lst1, lst2):
	return set(lst1).intersection(lst2)
for _ in range(t):
	n = int(input())
	pair = int(input())
	d = {}
	for value in range(pair):
		(a, b) = map(int, input().split())
		if a in d:
			d[a].append(b)
		else:
			d[a] = [b]
		if b in d:
			d[b].append(a)
		else:
			d[b] = [a]
	d = dict(sorted(d.items(), key=lambda item: len(item[1])))
	if n == 2:
		print(1)
		print(1, 1)
		print(1)
		continue
	for (key, value) in d.items():
		smallestKey = key
		break
	values = []
	values = d[smallestKey]
	totalValues = values.copy()
	totalValues.append(smallestKey)
	manager = []
	managerDict = {}
	for i in values:
		for j in d[i]:
			if j in totalValues:
				continue
			else:
				manager.append(j)
				manager.append(i)
	for (key, value) in d.items():
		if manager in value:
			manager.append(key)
	managerSet = set(manager.copy())
	manager = list(managerSet)
	for i in range(len(manager)):
		managerDict[manager[i]] = i + 1
	print(len(managerSet))
	ans = []
	for i in range(n):
		if i + 1 in manager:
			ans.append(managerDict[i + 1])
			continue
		common = Intersection(d[i + 1], manager).pop()
		ans.append(managerDict[common])
	print(*ans)
	print(*managerSet)


from collections import *
for _ in range(int(input())):
	n = int(input())
	d = [0] * (n + 1)
	arr = []
	q = int(input())
	gr = [[] for i in range(n + 1)]
	for i in range(q):
		arr.append(list(map(int, input().split())))
		d[arr[i][0]] += 1
		d[arr[i][1]] += 1
		gr[arr[i][0]].append(arr[i][1])
		gr[arr[i][1]].append(arr[i][0])
	new = []
	for i in range(1, n + 1):
		new.append([i, d[i]])
	new.sort(key=lambda x: x[-1], reverse=True)
	root = new[0][0]
	d = deque()
	d.append(root)
	par = [-1] * (n + 1)
	par[root] = root
	v = set()
	v.add(root)
	while d:
		x = d.popleft()
		for i in gr[x]:
			if i not in v:
				par[i] = x
				v.add(i)
				d.append(i)
	s = set()
	for i in range(1, n + 1):
		s.add(par[i])
	if -1 in s:
		s.remove(-1)
	print(len(s))
	he = sorted(list(s))
	d = defaultdict(lambda : 0)
	for i in range(len(he)):
		d[he[i]] = i + 1
		par[he[i]] = he[i]
	ans = [0] * (n + 1)
	for i in range(1, n + 1):
		ans[i] = d[par[i]]
	print(*ans[1:])
	print(*he)


y = lambda : map(int, input().split())
(t,) = y()
for _ in range(t):
	(n,) = y()
	(k,) = y()
	g = [[] for _ in range(n)]
	for _ in range(k):
		(u, v) = y()
		u -= 1
		v -= 1
		g[u].append(v)
		g[v].append(u)
	a = (*map(len, g),)
	u = a.index(min(a))
	r = [None] * n
	r[u] = 1
	for v in g[u]:
		r[v] = 1
		if a[v] > a[u]:
			u = v
	h = []
	for v in g[u]:
		if r[v] is None:
			h.append(v + 1)
			r[v] = len(h) + 1
	for v in h:
		for w in g[v - 1]:
			if r[w] is None:
				r[w] = r[v - 1]
	print(len(h) + 1)
	print(*r)
	print(u + 1, *h)


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

def find_manager(degrees, adj, idx):
	for neigh in adj[idx]:
		if degrees[neigh] > degrees[idx]:
			return neigh
	return None

def make_all_neighbours_of_non_manager_as_non_manager(adj, degrees, managers, idx, l):
	manager = find_manager(degrees, adj, idx)
	for neigh in adj[idx]:
		managers[neigh] = l
	managers[idx] = l
	return manager

def print_solution(managers, all_managers):
	print(len(all_managers))
	print(' '.join(list(map(str, managers[1:]))))
	print(' '.join(list(map(str, all_managers))))

def find_min_index(N, degrees, managers):
	min_val = N
	min_idx = -1
	for i in range(1, N + 1):
		if managers[i] == -1 and min_val > degrees[i]:
			min_val = degrees[i]
			min_idx = i
	return min_idx

def solution(N, adj, degrees, managers):
	all_managers = []
	while True:
		min_idx = find_min_index(N, degrees, managers)
		if min_idx == -1:
			print_solution(managers, all_managers)
			return
		manager = find_manager(degrees, adj, min_idx)
		all_managers.append(manager)
		make_all_neighbours_of_non_manager_as_non_manager(adj, degrees, managers, min_idx, len(all_managers))

def check_if_one_manager(mat, N):
	for i in range(1, N + 1):
		for j in range(i + 1, N + 1):
			if mat[i][j] == False:
				return False
	return True

def print_solution_for_single_manager(N):
	print(1)
	print(' '.join(list(map(str, [1] * N))))
	print(1)

def solve(N, C):
	adj = defaultdict(lambda : [])
	mat = [[False for _ in range(N + 1)] for _ in range(N + 1)]
	for (f, t) in C:
		adj[f].append(t)
		adj[t].append(f)
		mat[f][t] = True
		mat[t][f] = True
	if check_if_one_manager(mat, N):
		print_solution_for_single_manager(N)
		return
	degrees = [0 for _ in range(N + 1)]
	managers = [-1 for _ in range(N + 1)]
	for i in range(N + 1):
		degrees[i] = len(adj[i])
	solution(N, adj, degrees, managers)
for _ in range(t):
	N = int(input())
	K = int(input())
	C = []
	for _ in range(K):
		C.append(tuple(map(int, input().split())))
	solve(N, C)


from collections import defaultdict
from collections import defaultdict, deque, Counter
from itertools import groupby, accumulate, cycle, chain
from bisect import bisect_left, bisect_right
from math import inf
from string import ascii_lowercase, ascii_uppercase
from copy import deepcopy
from heapq import heapify, heappush, heappop
from functools import lru_cache
import re
T = int(input())
vt = lambda t: [t(num) for num in input().split()]
it = lambda : vt(int)[0]
st = lambda a: a.sort()

def run_tc():
	n = it()
	e = it()
	ind = defaultdict(int)
	adj = defaultdict(list)
	for _ in range(e):
		(u, v) = vt(int)
		ind[u] += 1
		ind[v] += 1
		adj[u].append(v)
		adj[v].append(u)
	S = sorted(ind.items(), key=lambda x: x[1])
	u = S[0][0]
	m = None
	for v in adj[u]:
		if ind[v] > ind[u]:
			m = v
			break
	if m is not None:
		mgr = [x for x in adj[m] if ind[x] != ind[u]]
		mgr += [m]
		mgr.sort()
		ans = [0] * n
		D = 1
		seen = set(mgr)
		for y in mgr:
			ans[y - 1] = D
			for v in adj[y]:
				if v not in seen:
					ans[v - 1] = D
					seen.add(v)
			D += 1
		print(len(mgr))
		print(*ans)
		print(*mgr)
	else:
		print(1)
		print(*[1] * n)
		print(1)
for _ in range(T):
	run_tc()


R = lambda : map(int, input().split())
(t,) = R()
for _ in range(t):
	(n,) = R()
	(k,) = R()
	g = [[] for _ in range(n)]
	for _ in range(k):
		(u, v) = R()
		u -= 1
		v -= 1
		g[u].append(v)
		g[v].append(u)
	r = [None] * n
	h = []
	for (l, u) in sorted(((len(x), i) for (i, x) in enumerate(g))):
		if r[u] is None:
			h.append(u + 1)
			r[u] = len(h)
			for v in g[u]:
				r[v] = r[u]
				if len(g[v]) > l:
					h[-1] = v + 1
	print(len(h))
	print(*r)
	print(*h)


import math
from bisect import bisect, bisect_left, bisect_right
import heapq
from math import gcd, floor, sqrt, log
from collections import defaultdict as ddc
from collections import Counter

def intin():
	return int(input())

def mapin():
	return map(int, input().split())

def strin():
	return input().split()
INF = 10 ** 20
mod = 1000000007

def LIS(arr, n):
	dp = [10 ** 9] * (n + 1)
	for ele in arr:
		dp[bisect_left(dp, ele)] = ele
	return bisect_left(dp, 10 ** 9)

def exponentiation(bas, exp, mod=1000000007):
	t = 1
	while exp > 0:
		if exp % 2 != 0:
			t = t * bas % mod
		bas = bas * bas % mod
		exp //= 2
	return t % mod

def MOD(p, q=1, mod=1000000007):
	expo = 0
	expo = mod - 2
	while expo:
		if expo & 1:
			p = p * q % mod
		q = q * q % mod
		expo >>= 1
	return p
yes = 'YES'
no = 'NO'
even = 'EVEN'
odd = 'ODD'

def process(graph, n, k):
	ans = [0] * n
	m = 1
	heads = set()
	head = ddc(int)
	for i in range(n):
		for v in graph[i]:
			if len(graph[i]) > len(graph[v]):
				heads.add(i)
				head[m] = i + 1
				ans[i] = m
				m += 1
				break
	if not heads:
		for i in range(n):
			ans[i] = m
		head[m] = 1
		m += 1
	else:
		for w in heads:
			for ww in heads:
				if w != ww:
					graph[w].discard(ww)
			for v in graph[w]:
				ans[v] = ans[w]
	print(m - 1)
	print(*ans)
	print(*[head[i] for i in range(1, m)])

def main():
	for _ in range(int(input())):
		n = intin()
		k = intin()
		graph = ddc(set)
		for i in range(k):
			(u, v) = mapin()
			graph[u - 1].add(v - 1)
			graph[v - 1].add(u - 1)
		process(graph, n, k)
main()


for _ in range(int(input())):
	N = int(input())
	K = int(input())
	graph_data = {x: [] for x in range(1, N + 1)}
	graph_degree = {x: 0 for x in range(1, N + 1)}
	for i in range(K):
		(u, v) = map(int, input().split())
		graph_data[u].append(v)
		graph_degree[u] += 1
		graph_data[v].append(u)
		graph_degree[v] += 1
	min_degree_node = min(graph_degree, key=graph_degree.get)
	min_degree = graph_degree[min_degree_node]
	head = 0
	visited = []
	visited.append(min_degree_node)
	if K == N * (N - 1) / 2:
		print(1)
		print('1 ' * N)
		print(1)
	else:
		for neighbour in graph_data[min_degree_node]:
			neighbour_degree = graph_degree[neighbour]
			if neighbour_degree > min_degree:
				head = neighbour
			visited.append(neighbour)
		visited.remove(head)
		head_list = []
		head_list.append(head)
		for neighbour in graph_data[head]:
			if neighbour not in visited:
				head_list.append(neighbour)
		head_list.sort()
		res = [0 for x in range(N)]
		l = 1
		for i in head_list:
			res[i - 1] = l
			for j in graph_data[i]:
				if j not in head_list:
					res[j - 1] = l
			l += 1
		print(len(head_list))
		print(*res)
		print(*head_list)


t = int(input())
for _ in range(t):
	N = int(input())
	K = int(input())
	edges = []
	graph = {}
	for _ in range(K):
		edges.append(tuple(map(int, input().split())))
	for (x, y) in edges:
		try:
			graph[x].append(y)
		except:
			graph[x] = [y]
		try:
			graph[y].append(x)
		except:
			graph[y] = [x]
	managers = set()
	maxi = 0
	md = -1
	for i in graph:
		if len(graph[i]) > maxi:
			maxi = len(graph[i])
			md = i
	managers.add(md)
	s = set(graph[md])
	s.add(md)

	def bfs(s, no):
		s1 = set(graph[graph[no][0]])
		s2 = set()
		s1.add(graph[no][0])
		for i in graph[no]:
			s2 = set(graph[i])
			s2.add(i)
			if s1 != s2:
				break
		for i in s1:
			if i not in s:
				break
		else:
			for i in s2:
				if i in s:
					managers.add(i)
			return
		for i in s1:
			if i in s:
				managers.add(i)
	bfs(s, md)
	if managers == s:
		print('1')
		print('1 ' * N)
		print('1')
	else:
		print(len(managers))
		s = ['0'] * N
		c = 1
		man = ''
		for i in managers:
			s[i - 1] = str(c)
			man += str(i) + ' '
			for j in graph[i]:
				if j not in managers:
					s[j - 1] = str(c)
			c += 1
		print(' '.join(s))
		print(man)


T = int(input())
for i in range(T):
	N = int(input())
	K = int(input())
	rel = {}
	deg = {}
	for j in range(K):
		(a, b) = list(map(int, input().strip().split(' ')))
		if a in rel:
			rel[a].append(b)
			deg[a] += 1
		else:
			rel[a] = [b]
			deg[a] = 1
		if b in rel:
			rel[b].append(a)
			deg[b] += 1
		else:
			rel[b] = [a]
			deg[b] = 1
	if K == N * (N - 1) // 2:
		print(1)
		print(('1 ' * N).strip())
		print(1)
	else:
		min_deg = N + 1
		min_deg_person = None
		for person in deg:
			if deg[person] < min_deg:
				min_deg = deg[person]
				min_deg_person = person
		M = []
		for frnd in rel[min_deg_person]:
			if deg[frnd] != deg[min_deg_person]:
				manager = frnd
				manager_grp = set(rel[frnd])
				manager_grp.add(frnd)
				employee_grp = set(rel[min_deg_person])
				employee_grp.add(min_deg_person)
				employee_grp.remove(frnd)
				M = list(manager_grp - employee_grp)
				break
		M.sort()
		ans = []
		for i in range(1, N + 1):
			if i in M:
				ans.append(M.index(i) + 1)
			else:
				man = list(set(M).intersection(set(rel[i])))
				ans.append(M.index(man[0]) + 1)
		print(len(M))
		gr = [str(w) for w in ans]
		gr = ' '.join(gr)
		ma = [str(w) for w in M]
		ma = ' '.join(ma)
		print(gr)
		print(ma)


from collections import Counter
import numpy as np

def inparr():
	tmparr = [int(i) for i in input().split()]
	return tmparr
for _ in range(int(input())):
	N = int(input())
	K = int(input())
	arr = np.zeros((N + 1, N + 1))
	for i in range(K):
		(x, y) = inparr()
		arr[y][x] = 1
		arr[x][y] = 1
	if N == 2:
		print('1\n1 1\n1\n')
		continue
	d1 = Counter()
	for i in range(1, N + 1):
		for j in range(1, N + 1):
			if arr[i][j]:
				d1[i] += 1
				d1[j] += 1
	minv = min(d1.values())
	minnode = 1
	dept1 = []
	for i in d1:
		if d1[i] == minv:
			dept1.append(i)
			break
	minnode = dept1[0]
	for i in range(1, N + 1):
		if arr[i][minnode]:
			dept1.append(i)
	headc = d1[minnode]
	head1 = 'na'
	for i in dept1:
		if d1[i] > headc:
			head1 = i
	d2 = Counter()
	dheads = [head1]
	for i in range(1, N + 1):
		if arr[i][head1]:
			if i not in dept1:
				dheads.append(i)
	office = [dept1]
	for i in dheads[1:]:
		tdept = [i]
		for j in range(1, N + 1):
			if arr[j][i] and j not in dheads:
				tdept.append(j)
		office.append(tdept)
	print(len(dheads))
	for i in range(len(dheads)):
		for j in office[i]:
			d2[j] = i + 1
	for i in range(1, N + 1):
		print(d2[i], end=' ')
	print()
	for i in dheads:
		print(i, end=' ')
	print()


from functools import cmp_to_key
from collections import Counter, deque, defaultdict, OrderedDict
import math
from bisect import bisect, bisect_left
import sys
import re
MOD = 10 ** 9 + 7
MAX = -sys.maxsize
MIN = sys.maxsize

class get:

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

	def str():
		return input().split()

	def float():
		return list(map(float, input().split()))

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

def sqrt(x):
	return int(math.sqrt(x)) + 1

def gcd(*args):
	result = args[0]
	for item in args:
		result = math.gcd(result, item)
	return result

def LCM(a, b):
	return a * b // math.gcd(a, b)

def isPrime(n):
	if n == 1:
		return False
	for i in range(2, sqrt(n)):
		if n % i == 0:
			return False
	return True

def solve():
	n = int(input())
	k = int(input())
	edge = defaultdict(set)
	(m, max_) = (0, 0)
	for _ in range(k):
		(a, b) = get.map()
		edge[a].add(b)
		edge[b].add(a)
		if len(edge[a]) > max_:
			max_ = len(edge[a])
			m = a
		if len(edge[b]) > max_:
			max_ = len(edge[b])
			m = b
	if k == n * (n - 1) // 2:
		print(1)
		print(*[1 for i in range(n)])
		print(1)
		return
	dep = {m: [1, [m]]}
	visited = set()
	visited.add(m)
	heads = deque([m])
	j = 1
	while len(heads) > 0:
		curr_head = heads.popleft()
		curr_dep = dep[curr_head][0]
		child_of_head = edge[curr_head]
		for item in child_of_head:
			if item not in visited:
				visited.add(item)
				child_of_item = edge[item]
				ss = child_of_item.intersection(child_of_head)
				ss.add(curr_head)
				if child_of_item == ss:
					dep[curr_head][1].append(item)
				else:
					dep[item] = [j + 1, [item]]
					j += 1
					heads.append(item)
	print(len(dep))
	emp = [0] * n
	heads = []
	for (a, b) in dep.items():
		heads.append(a)
		for item in b[1]:
			emp[item - 1] = b[0]
	print(*emp)
	print(*heads)
t = int(input())
for tt in range(t):
	solve()


import time
import sys
import math
(mod, infi) = (1000000007, sys.maxsize)
from collections import deque, Counter, defaultdict as dd
from itertools import accumulate
from functools import lru_cache, reduce
from operator import mul, add, sub, truediv, floordiv, lt, le, eq, ne, gt, xor, concat, getitem, pow, lshift
inty = lambda : int(input())
stringy = lambda : input().strip()
mappy = lambda : map(int, input().strip().split())
fmappy = lambda : map(float, input().strip().split())
listy = lambda : list(map(int, input().strip().split()))
sys.setrecursionlimit(10 ** 6)
tick = lambda : time.perf_counter()
logg = lambda a, b: math.log2(a) / math.log2(b)
acc = lambda x: list(accumulate(x))
sign = lambda x, y: x >= 0 and y >= 0 or (x < 0 and y < 0)
T = inty()
for _ in range(T):
	n = inty()
	k = inty()
	graph = dd(set)
	for _ in range(k):
		(u, v) = mappy()
		graph[u].add(v)
		graph[v].add(u)
	mini = infi
	start = 0
	for node in graph:
		if len(graph[node]) < mini:
			mini = len(graph[node])
			start = node
	head = set()
	for node in graph[start]:
		if len(graph[node]) > mini:
			head |= graph[node] - graph[start]
			head |= {node}
			head -= {start}
	if not head:
		head |= {1}
	z = [0] * n
	r = 1
	for node in head:
		for nnode in graph[node]:
			if nnode not in head:
				z[nnode - 1] = r
		z[node - 1] = r
		r += 1
	print(len(head))
	print(*z)
	print(*head)


for _ in range(int(input())):
	n = int(input())
	k = int(input())
	head = [[] for i in range(n + 1)]
	child = []
	nor = [{i} for i in range(n + 1)]
	final = [0] * (n + 1)
	fnlhead = []
	if n == 2:
		(a, b) = map(int, input().split())
		print(1)
		print(*[1, 1])
		print(a)
	else:
		for i in range(k):
			(a, b) = map(int, input().split())
			nor[a].add(b)
			nor[b].add(a)
		for i in range(1, n + 1):
			for j in nor[i]:
				if nor[i] < nor[j]:
					head[j].append(i)
		grp = 1
		for i in range(n + 1):
			if len(head[i]) != 0:
				final[i] = grp
				fnlhead.append(i)
				for j in head[i]:
					final[j] = grp
				grp += 1
		print(len(fnlhead))
		print(*final[1:])
		print(*fnlhead)


from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	k = int(input())
	gp = defaultdict(list)
	vis = [False for i in range(n + 1)]
	dep = 1
	grp = {}
	head = []
	visits = 0
	for i in range(k):
		(x, y) = [int(j) for j in input().split()]
		gp[x].append(y)
		gp[y].append(x)
	hd = 1
	for i in range(1, n + 1):
		if len(gp[i]) > len(gp[hd]):
			hd = i
	vis[hd] = True
	grp[hd] = dep
	for j in gp[hd]:
		vis[j] = True
		grp[j] = dep
	head.append(hd)
	for i in range(1, n + 1):
		if not vis[i]:
			dep += 1
			vis[i] = True
			grp[i] = dep
			for j in gp[i]:
				grp[j] = dep
				if vis[j]:
					head.append(j)
				vis[j] = True
	print(dep)
	for i in range(1, n + 1):
		print(grp[i], end=' ')
	print()
	for i in head:
		print(i, end=' ')
	print()


for _ in range(int(input())):
	n = int(input())
	k = int(input())
	nag = {}
	rels = [[] for i in range(n + 1)]
	for i in range(1, n + 1):
		nag[i] = 0
	for i in range(k):
		tupi = list(map(int, input().split()))
		nag[tupi[0]] += 1
		nag[tupi[1]] += 1
		rels[tupi[0]].append(tupi[1])
		rels[tupi[1]].append(tupi[0])
	minv = min(nag, key=nag.get)
	neib = set()
	neib.add(minv)
	leader = minv
	for i in rels[minv]:
		if nag[i] == nag[minv]:
			neib.add(i)
		else:
			leader = i
	answer = [-1 for i in range(n)]
	leaders = [leader]
	for i in rels[leader]:
		if i not in neib:
			leaders.append(i)
	for (i, j) in enumerate(leaders):
		answer[j - 1] = i + 1
		for yo in rels[j]:
			if yo not in set(leaders):
				answer[yo - 1] = i + 1
	print(len(leaders))
	print(*answer)
	print(*leaders)


m = int(input())
for i in range(m):
	n = int(input())
	k = int(input())
	d = {}
	l = [0 for j in range(n)]
	h = []
	if n == 2:
		l = [1, 1]
		h = [1]
	for j in range(k):
		z = input().split()
		if int(z[0]) in d:
			d[int(z[0])] += [int(z[1])]
		else:
			d[int(z[0])] = [int(z[1])]
		if int(z[1]) in d:
			d[int(z[1])] += [int(z[0])]
		else:
			d[int(z[1])] = [int(z[0])]
	b = 1
	for j in range(1, n + 1):
		if l[j - 1] == 0:
			t = d[j]
			p = 0
			for k in range(len(t)):
				if len(d[t[k]]) < len(t):
					p = 1
					y = t[k]
			if p != 1:
				l[j - 1] = b
				for k in range(len(t)):
					if len(d[t[k]]) > len(t):
						l[t[k] - 1] = b
						h += [t[k]]
					else:
						l[t[k] - 1] = b
				b += 1
	print(len(h))
	print(' '.join(map(str, l)))
	print(' '.join(map(str, h)))


n = int(input())
for i in range(n):
	e = int(input())
	c = int(input())
	d = {}
	for j in range(1, e + 1):
		d[j] = []
		d[j].append(j)
	for j in range(c):
		(x, y) = map(int, input().split())
		d[x].append(y)
		d[y].append(x)
	m = 1
	for j in range(1, e + 1):
		d[j].sort()
		if len(d[m]) < len(d[j]):
			m = j
	h = []
	h.append(m)
	for j in d[m]:
		f = 0
		for k in d[j]:
			if k in d[m]:
				pass
			else:
				f = 1
		if f == 1:
			h.append(j)
	print(len(h))
	l = []
	for j in range(1, e + 1):
		f = 0
		for k in range(len(h)):
			if j in d[h[k]] and j not in h:
				l.append(k + 1)
				break
		if j in h:
			l.append(h.index(j) + 1)
	print(*l)
	print(*h)


testcase = int(input())
for _ in range(testcase):
	n = int(input())
	k = int(input())
	graph = [set() for _ in range(n + 1)]
	for _ in range(k):
		(a, b) = [int(num) for num in input().split()]
		graph[a].add(b)
		graph[b].add(a)
	seen = set()
	arr = []
	deps = []
	for i in range(1, n + 1):
		arr.append((len(graph[i]), i))
	arr.sort(reverse=True)
	while arr:
		(t, i) = arr.pop()
		if i in seen:
			continue
		seen.add(i)
		dep = [i]
		for emp in graph[i]:
			if len(graph[emp]) == t:
				dep.append(emp)
			else:
				dep.insert(0, emp)
			seen.add(emp)
		deps.append(dep)
	ans1 = [0] * n
	for (ind, dep) in enumerate(deps):
		for emp in dep:
			ans1[emp - 1] = ind + 1
	ans2 = [dep[0] for dep in deps]
	print(len(deps))
	print(*ans1)
	print(*ans2)


for _ in range(int(input())):
	n = int(input())
	k = int(input())
	a = [[x] for x in range(n)]
	for i in range(k):
		(temp1, temp2) = map(int, input().split())
		a[temp1 - 1].append(temp2 - 1)
		a[temp2 - 1].append(temp1 - 1)
	big = -1
	pos = -1
	for i in range(n):
		if len(a[i]) > big:
			pos = i
			big = len(a[i])
	head = []
	for i in a[pos]:
		if set(a[i]).issubset(set(a[pos])):
			pass
		else:
			head.append(i)
	head.insert(0, pos)
	departs = [0 for x in range(len(head))]
	for i in range(len(departs)):
		departs[i] = list(set(a[head[i]]) - set(head))
		departs[i].append(head[i])
	emp_depart = [0 for x in range(n)]
	for i in range(len(head)):
		for j in departs[i]:
			emp_depart[j] = i + 1
		emp_depart[head[i]] = i + 1
	print(len(departs))
	print(*emp_depart)
	print(*[x + 1 for x in head])


from collections import *

def findNew(new, d):
	for i in range(1, n + 1):
		new.append([i, d[i]])
	new.sort(key=lambda x: x[-1], reverse=True)
	return new

def bfs(new, graph):
	root = new[0][0]
	d = deque()
	d.append(root)
	par = [-1] * (n + 1)
	par[root] = root
	v = set()
	v.add(root)
	while d:
		x = d.popleft()
		for i in graph[x]:
			if i not in v:
				par[i] = x
				v.add(i)
				d.append(i)
	s = set()
	for i in range(1, n + 1):
		s.add(par[i])
	if -1 in s:
		s.remove(-1)
	print(len(s))
	he = sorted(list(s))
	d = defaultdict(lambda : 0)
	for i in range(len(he)):
		d[he[i]] = i + 1
		par[he[i]] = he[i]
	return (d, par, he)
for _ in range(int(input())):
	n = int(input())
	d = [0] * (n + 1)
	arr = []
	q = int(input())
	graph = [[] for i in range(n + 1)]

	def makegraph():
		for i in range(q):
			arr.append(list(map(int, input().split())))
			d[arr[i][0]] += 1
			d[arr[i][1]] += 1
			graph[arr[i][0]].append(arr[i][1])
			graph[arr[i][1]].append(arr[i][0])
	makegraph()
	neww = findNew([], d)
	(d, par, he) = bfs(neww, graph)
	ans = [0] * (n + 1)
	for i in range(1, n + 1):
		ans[i] = d[par[i]]
	print(*ans[1:])
	print(*he)


from math import *
import sys

def input():
	return sys.stdin.readline().replace('\n', '').strip()
sys.setrecursionlimit(10 ** 9)
for _ in range(int(input())):
	n = int(input())
	k = int(input())
	graph = {}
	for i in range(1, n + 1):
		graph[i] = []
	degree = [0 for i in range(n + 1)]
	dept = [0 for i in range(n)]
	pair_l = []
	for i in range(k):
		(u, v) = list(map(int, input().split()))
		graph[u].append(v)
		graph[v].append(u)
		degree[u] += 1
		degree[v] += 1
	for i in range(1, n + 1):
		pair_l.append((degree[i], i))
	(deg, emp) = min(pair_l)
	heads = []
	count = 1
	dept[emp - 1] = count
	head1 = -1
	for i in graph[emp]:
		if degree[i] != degree[emp]:
			head1 = i
			heads.append(head1)
		dept[i - 1] = count
	if head1 == -1:
		head1 = emp
		heads.append(head1)
	count = 2
	for i in graph[head1]:
		if dept[i - 1] == 0:
			heads.append(i)
			dept[i - 1] = count
			count += 1
	for j in heads:
		for k in graph[j]:
			if dept[k - 1] == 0:
				dept[k - 1] = dept[j - 1]
	print(len(heads))
	print(*dept)
	print(*heads)


for _ in range(int(input())):
	n = int(input())
	k = int(input())
	adj_list = {}
	dept = {}
	for i in range(1, n + 1):
		adj_list[i] = []
		dept[i] = 0
	for _ in range(k):
		(u, v) = map(int, input().split())
		adj_list[u].append(v)
		adj_list[v].append(u)
	dept_heads = []
	dept_count = 0
	remaining = True
	next_vertex = 1
	while remaining:
		ngbrs_count = len(adj_list[next_vertex])
		curr_vertex = next_vertex
		curr_vertices = [next_vertex]
		while True:
			for u in adj_list[curr_vertices[-1]]:
				if len(adj_list[u]) < ngbrs_count and dept[u] == 0:
					ngbrs_count = len(adj_list[u])
					curr_vertex = u
			curr_vertices.append(curr_vertex)
			ngbrs_count = len(adj_list[curr_vertex])
			if curr_vertices[-1] == curr_vertices[-2]:
				break
		dept_count += 1
		dept[curr_vertex] = dept_count
		for u in adj_list[curr_vertex]:
			dept[u] = dept_count
			if len(adj_list[u]) > len(adj_list[curr_vertex]):
				dept_heads.append(u)
		for i in range(1, n + 1):
			if dept[i] == 0:
				next_vertex = i
				break
		else:
			remaining = False
	print(dept_count)
	for i in range(1, n + 1):
		print(dept[i], end=' ')
	print()
	if dept_heads == []:
		print(1)
	else:
		for x in dept_heads:
			print(x, end=' ')
		print()


import sys, math, heapq, bisect
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 5)
ints = lambda : list(map(int, input().split()))

def gprint(t, ans=''):
	print(f'Case #{t + 1}:', ans)
p = 10 ** 9 + 7
inf = 10 ** 20 + 7

def check(node):
	store = set(graph[node])
	store.add(node)
	par = [node]
	for i in graph[node]:
		v = 1
		for j in graph[i]:
			if j not in store:
				v = 0
				break
		if v == 0:
			par.append(i)
	print(len(par))
	done = set(par)
	ans = [-1] * n
	c = 1
	for i in par:
		ans[i - 1] = c
		for j in graph[i]:
			if j not in done:
				ans[j - 1] = c
		c += 1
	print(*ans)
	print(*par)
for t in range(int(input())):
	n = int(input())
	m = int(input())
	graph = [[] for i in range(n + 1)]
	for i in range(m):
		(x, y) = ints()
		graph[x].append(y)
		graph[y].append(x)
	a = [[len(graph[i]), i] for i in range(1, n + 1)]
	a.sort()
	x = a.pop()[1]
	check(x)


import random
import math
from collections import defaultdict, Counter, deque, OrderedDict
from functools import lru_cache
import bisect
import heapq
import sys
input = sys.stdin.readline

class SegmentTree:

	def __init__(self, nums):
		self._size = len(nums)
		self._tree = [0] * (4 * self._size)
		self.build(nums)

	def build(self, a, v=1, lo=0, hi=None):
		if hi is None:
			hi = self._size - 1
		if lo == hi:
			self._tree[v] = a[lo]
		else:
			mi = (lo + hi) // 2
			self.build(a, 2 * v, lo, mi)
			self.build(a, 2 * v + 1, mi + 1, hi)
			self._tree[v] = self._tree[2 * v] + self._tree[2 * v + 1]

	def update(self, pos, val, v=1, lo=0, hi=None):
		if hi is None:
			hi = self._size - 1
		if lo == hi:
			self._tree[v] = val
		else:
			mi = (lo + hi) // 2
			if pos <= mi:
				self.update(pos, val, 2 * v, lo, mi)
			else:
				self.update(pos, val, 2 * v + 1, mi + 1, hi)
			self._tree[v] = self._tree[2 * v] + self._tree[2 * v + 1]

	def query(self, l, h, v=1, lo=0, hi=None):
		if hi is None:
			hi = self._size - 1
		if l > h:
			return 0
		elif l == lo and h == hi:
			return self._tree[v]
		else:
			mi = (lo + hi) // 2
			return self.query(l, min(mi, h), 2 * v, lo, mi) + self.query(max(mi + 1, l), h, 2 * v + 1, mi + 1, hi)

class UnionFind:

	def __init__(self, n):
		self.n = n
		self.parents = list(range(n))

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

	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x != y:
			self.parents[x] = y
dire = [0, 1, 0, -1, 0]

def is_prime(n):
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return False
	return True

def case(t):
	print('Case #{}:'.format(t), end=' ')
RANDOM = random.randrange(2 ** 62)

def Wrapper(x):
	return x ^ RANDOM

def solve():
	n = int(input())
	p = int(input())
	mapp = defaultdict(set)
	for i in range(p):
		(a, b) = map(int, input().split())
		mapp[a].add(b)
		mapp[b].add(a)
	heads = set()
	for i in range(1, n + 1):
		tobreak = False
		for j in mapp[i]:
			allexist = True
			for k in mapp[j]:
				if k not in mapp[i] and k != i:
					allexist = False
					break
			if allexist and len(mapp[i]) > len(mapp[j]):
				heads.add(i)
				for k in mapp[i]:
					if k not in mapp[j] and k != j:
						heads.add(k)
				tobreak = True
				break
		if tobreak:
			break
	if len(heads) == 0:
		print(1)
		print(*[1] * n)
		print(1)
		return
	heads = list(heads)
	headmap = {}
	for i in range(len(heads)):
		headmap[heads[i]] = i + 1
	print(len(heads))
	for i in range(1, n + 1):
		if i in heads:
			print(headmap[i], end=' ')
		else:
			for j in mapp[i]:
				if j in heads:
					print(headmap[j], end=' ')
	print()
	print(*heads)
for t in range(int(input())):
	solve()


for tc in range(int(input())):
	m = int(input())
	k = int(input())
	d = dict.fromkeys(range(1, m + 1), None)
	a = dict.fromkeys(range(1, m + 1), None)
	for i in range(1, k + 1):
		(p1, p2) = map(int, input().split())
		if d[p1] is None:
			d[p1] = set()
		if d[p2] is None:
			d[p2] = set()
		d[p1].add(p2)
		d[p2].add(p1)
	h = list()
	c = 1
	for i in range(1, m + 1):
		if a[i] is not None:
			continue
		p1 = d[i]
		not_lead = False
		if len(p1) == 1:
			not_lead = True
		else:
			for j in p1:
				p2 = d[j]
				if len(p1 ^ p2) == 2:
					not_lead = True
		if not_lead:
			a[i] = c
			for j in p1:
				a[j] = c
				if len(d[j]) > len(p1):
					h.append(j)
			if len(h) < c:
				h.append(i)
			c += 1
	print(c - 1)
	print(' '.join((str(x) for x in a.values())))
	print(' '.join((str(x) for x in h)))


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

def facto(n):
	ans = 1
	while n:
		ans = ans * 2 % mod
	return ans

class Solve:

	def __init__(self, n, k):
		self.n = n
		self.k = k
		self.st = set()

	def dp(self, ones, zeroes):
		if ones < 0 or zeroes < 0:
			return
		if ones in self.st:
			return
		self.st.add(ones)
		for i in range(zeroes + 1):
			if ones >= self.k - i:
				self.dp(ones + i - (self.k - i), zeroes - i + (self.k - i))
		for i in range(ones + 1):
			if zeroes >= self.k - i:
				self.dp(ones - i + (self.k - i), zeroes + i - (self.k - i))

def solve():
	n = int(input())
	k = int(input())
	hs = defaultdict(lambda : set())
	queries = []
	for _ in range(k):
		(alpha, beta) = map(int, input().split())
		queries.append((alpha, beta))
		hs[alpha].add(beta)
		hs[beta].add(alpha)
	groups = []
	managers = set()
	ans = defaultdict(int)
	unique = 0
	for q in queries:
		(a, b) = q
		if len(hs[a]) > len(hs[b]):
			if len(hs[b].difference(hs[a].union({a}))) == 0:
				managers.add(a)
		elif len(hs[b]) > len(hs[a]):
			if len(hs[a].difference(hs[b].union({b}))) == 0:
				managers.add(b)
		else:
			pass
	ans = defaultdict(int)
	ansb = []
	for (i, x) in enumerate(managers):
		ansb.append(x)
		ans[x] = i + 1
		for y in hs[x]:
			if y not in managers:
				ans[y] = i + 1
	if len(ansb) == 0:
		print(1)
		print(' '.join(['1' for x in range(n)]))
		print(1)
	else:
		print(len(ansb))
		print(' '.join([str(ans[x + 1]) for x in range(n)]))
		print(' '.join([str(x) for x in ansb]))
for _ in range(int(input())):
	solve()


mod = 10 ** 9 + 7
t = int(input())
for t0 in range(t):
	n = int(input())
	k = int(input())
	pairs = []
	adjacent = {}
	for i in range(k):
		pair = list(map(int, input().split()))
		if not adjacent.__contains__(pair[0]):
			adjacent[pair[0]] = set()
		if not adjacent.__contains__(pair[1]):
			adjacent[pair[1]] = set()
		adjacent[pair[0]].add(pair[1])
		adjacent[pair[1]].add(pair[0])
		pairs.append(pair)
	heads = set()
	for pair in pairs:
		if len(adjacent[pair[0]]) > len(adjacent[pair[1]]):
			heads.add(pair[0])
		if len(adjacent[pair[1]]) > len(adjacent[pair[0]]):
			heads.add(pair[1])
	if len(heads) == 0:
		print(1)
		print(' '.join([str(item) for item in [1] * n]))
		print(1)
		continue
	if len(heads) == 1:
		a = set()
		b = set()
		good_head = list(heads)[0]
		reminded_nodes = list(adjacent[good_head])
		a_cap = reminded_nodes[0]
		a.add(a_cap)
		for i in range(1, len(reminded_nodes)):
			node = reminded_nodes[i]
			if adjacent[node].__contains__(a_cap):
				a.add(node)
			else:
				b.add(node)
		dep_num = {good_head: 1}
		counter = 2
		for head in a:
			dep_num[head] = counter
			counter += 1
		for node in b:
			dep_num[node] = 1
		print(2)
		print(' '.join([str(dep_num[node]) for node in range(1, n + 1)]))
		all_heads = list(a)
		all_heads.append(good_head)
		print(' '.join([str(head) for head in all_heads]))
		continue
	head_of_node = {}
	for node in range(1, n + 1):
		if heads.__contains__(node):
			continue
		for adj in adjacent[node]:
			if heads.__contains__(adj):
				if head_of_node.__contains__(node):
					del head_of_node[node]
					heads.add(node)
					break
				else:
					head_of_node[node] = adj
	dep_num = {}
	counter = 1
	for head in heads:
		dep_num[head] = counter
		counter += 1
	print(len(heads))
	line2 = []
	for node in range(1, n + 1):
		if heads.__contains__(node):
			head = node
		else:
			head = head_of_node[node]
		line2.append(str(dep_num[head]))
	print(' '.join(line2))
	print(' '.join([str(head) for head in heads]))


from collections import *
for _ in range(int(input())):
	n = int(input())
	k = int(input())
	q = defaultdict(set)
	for i in range(k):
		(x, y) = map(int, input().split())
		q[x].add(y)
		q[y].add(x)
	o = 100000
	x = 1
	for i in q:
		if len(q[i]) < o:
			o = len(q[i])
			x = i
	head = set()
	for j in q[x]:
		if len(q[j]) > o:
			head |= q[j] - q[x]
			head |= {j}
			head -= {x}
			break
	if not head:
		head |= {1}
	z = [0] * n
	r = 1
	for i in head:
		for j in q[i]:
			if j not in head:
				z[j - 1] = r
		z[i - 1] = r
		r += 1
	print(len(head))
	print(*z)
	print(*head)


tc = int(input())
for _ in range(tc):
	n = int(input())
	k = int(input())
	adjl = [set() for _ in range(n)]
	for i in range(k):
		(u, v) = map(int, input().split())
		adjl[u - 1].add(v - 1)
		adjl[v - 1].add(u - 1)
	maxd = 0
	md = -1
	for i in range(n):
		if len(adjl[i]) > maxd:
			maxd = len(adjl[i])
			md = i
	p = set(adjl[md])
	start = p.pop()
	p = set(adjl[start])
	p.remove(md)
	p.add(start)
	if len(p.difference(adjl[md])) == 0:
		managers = adjl[md].difference(p)
	else:
		managers = adjl[md].intersection(p)
	managers.add(md)
	m = len(managers)
	print(m)
	d = [0 for i in range(n)]
	k = 1
	manx = list(managers)
	for tm in manx:
		d[tm] = k
		for v in adjl[tm]:
			if not v in managers:
				d[v] = k
		k += 1
	print(*d)
	print(*[t + 1 for t in manx])