**Link to the question:** https://www.codechef.com/JAN19A/problems/GRAPART

**Given TestCases Explanation:**

**INPUT :**

2

2

1 2

6

1 2

1 3

3 4

3 5

3 6

**OUTPUT :**

1

1

2

2

1 3 5

2 4 6

**Case 1:**

No explanation needed

Set 1 : 1

Set 2 : 2

**Case 2**

for k = 2

**Hk** edges

**Distance 1 :**

1 2

1 3

3 4

3 5

3 6

**Distance 2 :**

1 4

1 5

1 6

2 3

4 5

4 6

5 6

After forming sets

**Edges in the good graph (E)**

1 2

3 4

3 6

1 4

1 6

2 3

4 5

5 6

** SOLUTION:**

If solution have **k** = 1

Then for the graph to be connected. **Parent of all nodes should be in a different set.**

This can be done simply by using a simple **DFS** function

```
DFS (int nd,vector<int> adj[],int flag,int par,vector<int> ans[]){
ans[flag].push_back(nd);
if(flag == 0)
flag = 1;
else
flag = 0;
for(int i = 0;i < adj[nd].size();i++){
if(adj[nd][i] != par)
DFS(adj[nd][i],adj,flag,nd,ans);
}
}
```

If the size of both sets is equal. Then **k** = 1 and both the sets are an answer.

**Special Case**

If the graph is a **degenerate tree** like a graph with edges

1 2

2 3

3 4

4 5

5 6

**set u:** 1 3 5

**set v:** 2 4 6

Therefore for a solution, **adjacent nodes are put in different sets.**

**General Case:**

For **k** = 2 having an answer is always possible.

**Explanation**

**Single path of DFS is a degenerate tree**

Algorithm used

First, take root node as **ND** and start moving from **ND** to a leaf node and keep storing the **path (Let it be P)**.

After reaching the leaf node. Adjacent nodes in **P** get in different sets.

All the nodes in **P** are visited and can’t be part of any other path.

If there is any node connected with a visited node and is not visited itself.

Then take that node as **ND** and clear **P**.

Move from **ND** to a leaf node and keep storing the **path (Let it be P)** which contains only elements which are not visited yet.

After reaching the leaf node our **P** is completed.

**IMPORTANT OBSERVATIONS :**

We can start putting elements of **P**. To **U** or **V** any one of them. As suppose **ND** is connected to

**R (the node of the previous path)**. So If **R** belongs to **U** then Child of **R** or Parent of **R** belongs to **V** or vice versa. As **k** = 2, therefore, **ND** is connected to **R**, Child of **R** and Parent of **R**. So **P** would connect to already existing graph always. **(therefore for k = 2 answers always exists, k = 2 is maximum possible value of k).**

**Using the given technique or algorithm Difference between the size of sets would be at max 1.**

If the number of elements in **P** is even then, Adjacent elements of **P** get in different sets. (any order)

If the number of elements in **P** is odd and the number of elements of Both the sets are equal then Adjacent elements of **P** get in different sets. (any order)

If the number of elements in **P** is odd and the number of elements of Both sets is not equal. Then

**ND** get in the set with the lesser number of elements and other elements get in sets such that adjacent elements of **P** are in different sets.

As this would result in Size of **U** = Size of **V**.

For example, If the size of **U** = 3 and size of **V** = 2 and We have a **P** with size 3.Then we would Put **ND** in **V**( other elements alternatively ).

Resulting in size of **U** = size of **V** = 4 finally.

*TAKING EXAMPLE FOR CLARIFICATION OF EXPLANATION : *

Take a graph **G** with the number of nodes **N** = 10

Edges of **G** :

1 2

2 3

3 4

4 5

1 6

6 7

4 8

8 9

9 10

**SOLUTION**

For **k** = 2

First, take *ND* = 1 and Make a Path from 1 to 5 (**P** = 1 ,2 ,3 ,4 ,5).

Odd position elements get in **U** and even position elements get in **V**.

Set **U** : 1 3 5

Set **V** : 2 4

Mark 1,2,3,4,5 as visited and Clear **P**.

Taking **ND** = 8 ( As it is not visited yet and It is connected to a visited element ‘3’).

Make a Path from 8 to 10, therefore, P = 8 9 10.

As **k** = 2 therefore 8 is connected with 3,4,5.Therefore If we put odd position elements in **U** and even position elements in **V** or vice versa. The Graph would always remain connected.

As P size is odd and size of **U** is not equal to size of **V**.

So, Odd position elements get in Set which has a smaller size. (As elements at an odd position are more).

After putting the elements:

set U : 1 3 5 9

set V : 2 4 8 10

Mark 8,9,10 as visited and Clear **P**.

Taking **ND** = 6 ( As it is not visited yet and It is connected to a visited element ‘1’).

Make a Path from 6 to 7, therefore, P = 6 7.

As **k** = 2 therefore 6 is connected with 1,2.Therefore If we put odd position elements in U and even position elements in V or vice versa. The Graph would always remain connected.

As size of **P** is even, therefore, we can elements in any order alternatively.

After putting the elements :

set U: 1 3 5 9 6

set V: 2 4 8 10 7

Mark 6,7 as visited and

**A possible answer is**

**2

1 3 5 9 6

2 4 8 10 7**

**ACCEPTED CODE:**

PLEASE THUMBS UP. If you are able to understand the editorial.

If any doubts/suggestion please put them below.