## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

# [Solution] Departments (Easy Version) CodeChef Solution

## Problem

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

Solution Click Below:-  👉
👇👇👇👇👇

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 \leq D_i \leq 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 \leq H_i \leq 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.