You have n gardens, labeled from 1 to n, and an array paths where paths[i] = [xi, yi] describes a bidirectional path between garden xi to garden yi. In each garden, you want to plant one of 4 types of flowers.

All gardens have at most 3 paths coming into or leaving it.

Your task is to choose a flower type for each garden such that, for any two gardens connected by a path, they have different types of flowers.

Return any such a choice as an array answer, where answer[i] is the type of flower planted in the (i+1)th garden. The flower types are denoted 1, 2, 3, or 4. It is guaranteed an answer exists.

&nbsp;
Example 1:

Input: n = 3, paths = [[1,2],[2,3],[3,1]]
Output: [1,2,3]
Explanation:
Gardens 1 and 2 have different types.
Gardens 2 and 3 have different types.
Gardens 3 and 1 have different types.
Hence, [1,2,3] is a valid answer. Other valid answers include [1,2,4], [1,4,2], and [3,2,1].


Example 2:

Input: n = 4, paths = [[1,2],[3,4]]
Output: [1,2,1,2]


Example 3:

Input: n = 4, paths = [[1,2],[2,3],[3,4],[4,1],[1,3],[2,4]]
Output: [1,2,3,4]


&nbsp;
Constraints:


	1 &lt;= n &lt;= 104
	0 &lt;= paths.length &lt;= 2 * 104
	paths[i].length == 2
	1 &lt;= xi, yi &lt;= n
	xi != yi
	Every garden has at most 3 paths coming into or leaving it.


class Solution:
	def gardenNoAdj(self, n: int, paths: List[List[int]]) -> List[int]:
		g = defaultdict(list)
		for u,v in paths:
			g[u-1].append(v-1)            
			g[v-1].append(u-1) 
		ans = [0]*n
		for i in range(n):
			c = [1,2,3,4]
			for j in g[i]:
				if ans[j] in c: c.remove(ans[j])
			ans[i] = c.pop()
		return ans
class Solution {
    public int[] gardenNoAdj(int n, int[][] paths) {
        boolean[][] graph = new boolean[n][n];
        for(int i = 0;i<paths.length;i++){
            int u = paths[i][0]-1;
            int v = paths[i][1]-1;
            graph[u][v] = true;
            graph[v][u] = true;
        }
        int[] colored = new int[n];
        boolean[] available = new boolean[4];
        Arrays.fill(colored,-1);
        colored[0] = 1;
        for(int i = 1;i<n;i++){
            for(int j = 0;j<n;j++){
                if(graph[i][j] && colored[j]!=-1){
                    available[colored[j]-1]=true;
                }
            }
            int k,flag = 0;
            for(k = 0;k<4;k++){
                if(available[k]==false){
                    flag = 1;
                    break;
                }
            }
            colored[i] = k+1;
            Arrays.fill(available,false);
        }
        return colored;
    }
}
class Solution {
public:
    int check(vector<int> a[],vector<int> &col,int sv,int i)
    {
        for(auto it:a[sv])
        {
            if(col[it]==i)return 0;
        }
        return 1;
    }
    
    void dfs(vector<int> a[],vector<int> &col,int sv,int lc)
    {
        for(int i = 1;i<5;i++)
        {
            if(check(a,col,sv,i))
            {
                col[sv] = i;
                break;
            }
        }
        for(auto it:a[sv])
        {
            if(col[it]==-1)
            {
                dfs(a,col,it,col[sv]);
            }
        }
    }
    vector<int> gardenNoAdj(int n, vector<vector<int>>& paths) {
        vector<int> a[n];
        for(auto it:paths)
        {
            a[it[0]-1].push_back(it[1]-1);
            a[it[1]-1].push_back(it[0]-1);
        }
        
        vector<int> col(n,-1);
        for(int i = 0;i<n;i++)
        {
            if(col[i]==-1)
            {
                dfs(a,col,i,-7);
            }
        }
        return col;
    }
};
/**
 * @param {number} n
 * @param {number[][]} paths
 * @return {number[]}
 */
var gardenNoAdj = function(n, paths) {
    //if n is less than or equal to four just return an array of size n from 1 to n
    if(n <= 4){
        let arr = []
        let count = 1
        while(arr.length < n){
            arr.push(count)
            count++
        }
        return arr
    }
    //if there are no gardens connecting to each other then just return an array of size n with ones
    if(paths.length === 0)return new Array(n).fill(1)

    //because we have three possible paths connecting to gardens and 4 flowers we know that this problems is possible because our graph is of degree 3 and we have D + 1 flowers
    //to solve
    let adjList = {}
    // create an array filled with ones so if there is a garden with no path just fill with one
    let result = new Array(n).fill(1)
    let garden = new Set([1,2,3,4])

    //create adj list from the paths
    paths.forEach(path => {
        let first = path[0];
        let second = path[1];

        if(first in adjList )adjList[first].neighbors.add(second)
        else {adjList[first] = new Fnode(second)}

        if(second in adjList)adjList[second].neighbors.add(first)
        else {adjList[second] = new Fnode(first)}

    })

    for(let node in adjList){
        //every node
        let current = adjList[node]

        //create a set of invalid flowers, flowers you can't use because they are part of
        //the other gardens this one is connected to.
        let invalidFlower = new Set();

        //iterate over the neighbors to find what type of flower they have and if it is not
        //null included in the invalid flowers set
        current.neighbors.forEach(neighbor => {
            if(adjList[neighbor]['flower'] !== null){
                invalidFlower.add(adjList[neighbor]['flower'])
            }
        })

        //create our possible value or better said our value because we will use the first one
        //we obtain.
        let possibleFlower;

        //we iterate over over our garden {1,2,3,4}
        for(let flower of garden) {
            //and if our flower is not part of the invalid flowers;
            if(!invalidFlower.has(flower)){
                //we have found a possible flower we can use
                possibleFlower = flower
                //we break because this is the only one we need
                break;
            }
        }
        // we add our flower to current so that we dont use it in the future
        current.flower = possibleFlower

        //and update our result
        result[node - 1] = possibleFlower
    }
    //we return our result
    return result

};

//create a Flower class just for simplicity
class Fnode{
    constructor(neighbor){
        this.flower = null
        this.neighbors = new Set([neighbor])
    }
}
Flower Planting With No Adjacent