**PROBLEM LINK:**

https://www.codechef.com/CDGK2022/problems/COLORMAP

* Author:* kick_jayanth

*kirtana01, vamshi365, harisankar14, lokesh_la9, gayathrii*

**Testers:***bvsyaswanth1, kick_jayanth*

**Editorialist:****DIFFICULTY:**

TBD

**PREREQUISITES:**

Discrete Mathematical Structures

**PROBLEM:**

Chef wants to paint a map of his country. The map contains N number of states. He wants to paint it in such a way that, no two adjacent states are of same color. Help chef find the minimum number of colors required to paint the map.

**EXPLANATION:**

This problem is based on the famous four-color theorem. It says that, no more than four colors are required to color the regions of any map so that no two adjacent regions have the same color.

So, if N is 1, then we require only 1 color to paint the map. If N is 2, then we need 2 different colors since the 2 states will be adjacent to each other. Similarly, if N is 3, then we need 3 colors as all the 3 states might be adjacent to each other. Finally, if N=4 then we will need 4 colors as there is a chance that the 4 states might be adjacent to each other.

Now according to the four-color theorem, for all N>=5 we will need only 4 different colors so that no 2 adjacent states have same color.

**TIME COMPLEXITY:**

O(1) per test case

**CODE(Python):**

for _ in range(int(input())):

n = int(input())

print( n if n<=4 else 4)

**CODE(C++):**

#include < iostream>

using namespace std;

int main() {

int t;

cin>>t;

while(tâ€“){

int n;

cin>>n;

if(n<=4){

cout<<n<<endl;

}

else{

cout<<4<<endl;

}

}

return 0;

}