<p>You have <code>n</code> gardens, labeled from <code>1</code> to <code>n</code>, and an array <code>paths</code> where <code>paths[i] = [x<sub>i</sub>, y<sub>i</sub>]</code> describes a bidirectional path between garden <code>x<sub>i</sub></code> to garden <code>y<sub>i</sub></code>. In each garden, you want to plant one of 4 types of flowers.</p>

<p>All gardens have <strong>at most 3</strong> paths coming into or leaving it.</p>

<p>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.</p>

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

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> n = 3, paths = [[1,2],[2,3],[3,1]]
<strong>Output:</strong> [1,2,3]
<strong>Explanation:</strong>
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].
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> n = 4, paths = [[1,2],[3,4]]
<strong>Output:</strong> [1,2,1,2]
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> n = 4, paths = [[1,2],[2,3],[3,4],[4,1],[1,3],[2,4]]
<strong>Output:</strong> [1,2,3,4]
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 10<sup>4</sup></code></li>
	<li><code>0 &lt;= paths.length &lt;= 2 * 10<sup>4</sup></code></li>
	<li><code>paths[i].length == 2</code></li>
	<li><code>1 &lt;= x<sub>i</sub>, y<sub>i</sub> &lt;= n</code></li>
	<li><code>x<sub>i</sub> != y<sub>i</sub></code></li>
	<li>Every garden has <strong>at most 3</strong> paths coming into or leaving it.</li>
</ul>

class Solution {
public:    
    void bfs(int node1, vector<int>&clr, vector<int>adj[])
    {
        queue<pair<int,int>>q;
        q.push({node1,1});
   
        while(!q.empty())
        {
            int node = q.front().first;
            int colour = q.front().second;
            q.pop();
            
         //   ss.insert(colour);

            for(auto it : adj[node])
            {
                if(clr[it] == 0)
                {   
                    set<int>ss;
                   // ss.insert(colour);
                    for(auto i : adj[it])
                    {
                        if(clr[i] != 0)ss.insert(clr[i]);
                    }   
                  //  cout<<node+1<<" "<<it+1<<endl;
                    if(ss.find(1) == ss.end())
                    {
                        cout<<it;
                        clr[it]=1;
                        ss.insert(1);
                        q.push({it,1});
                    }
                    else if(ss.find(2) == ss.end())
                    {
                        ss.insert(2);
                        clr[it]=2;
                        q.push({it,2});
                    }
                    else if(ss.find(3) == ss.end())
                    {
                        ss.insert(3);
                        clr[it]=3;
                        q.push({it,3});
                    }
                    else if(ss.find(4) == ss.end())
                    {
                        ss.insert(4);
                        clr[it]=4;
                        q.push({it,4});
                    }
                
                }
            }
          
            
        }
        
    }
    vector<int> gardenNoAdj(int n, vector<vector<int>>& paths) {
        vector<int>adj[n];
        for(auto i : paths)
        {
            adj[i[0]-1].push_back(i[1]-1);
            adj[i[1]-1].push_back(i[0]-1);
        }
        vector<int>clr(n);
       
        queue<pair<int,int>>q;
        for(int i=0 ; i<n ; i++)
        {
            if(clr[i]==0)
            {
                
                clr[i]=1;
                bfs(i, clr, adj);
            }
        }
        
        
        return clr;
    }
};
76925