<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 dfs(int node,int val,vector<int>&visit,vector<int>adj[],vector<int>&color)
    {
        set<int>st={1,2,3,4};

        visit[node]=1;
        for(auto nbr:adj[node])
        {
            st.erase(color[nbr]);
        }
        color[node]=*st.begin();

        for(auto nbr:adj[node])
        {
            if(visit[nbr]==0)
            {
                dfs(nbr,color[node]+1,visit,adj,color);
            }

        }
    
    }

    vector<int> gardenNoAdj(int n, vector<vector<int>>& paths) {
        
        vector<int>adj[n+1];

        for(int i=0;i<paths.size();i++)
        {
            adj[paths[i][0]].push_back(paths[i][1]);
            adj[paths[i][1]].push_back(paths[i][0]);

        }
        vector<int>color(n+1,0);
        vector<int>visit(n+1,0);

        for(int i=1;i<n+1;i++)
        {
          if(visit[i]==0)
          {

          dfs(i,1,visit,adj,color);
          }

        }

        //  return color;

        // for(int i=1;i<n+1;i++)
        // {
        //     int col=(1^2^3^4);
        //     for(int j=0;j<adj[i].size();j++)
        //     {
        //         col=col^color[adj[i][j]];
                
        //     }

        //     for(int j=0;j<adj[i].size();j++)
        //     {
        //         if(color[i]==color[adj[i][j]])
        //         {
        //             color[adj[i][j]]=col;
        //         }   
        //     }

        // }

       

        vector<int>ans(color.begin()+1,color.end());

        return ans;

        // vector<int>visit(n+1,0);
        // vector<int>color(n+1,0);
        // int sum=1;
        // queue<pair<int,int>>q;
        // q.push({1,sum});
        // color[1]=sum;

        // while(q.size()>0)
        // {
        //     int size=q.size();
            
        //     for(int i=0;i<size;i++)
        //     {
        //         int node=q.front().first;
        //         int colorofnode=q.front().second;
        //         q.pop();

        //         cout<<"node is "<<node<<endl;

        //         for(auto nbr :adj[node])
        //         {
        //             if(visit[nbr]==0)
        //             {
        //                 visit[nbr]=1;
        //                 if(colorofnode==4)
        //                 {
        //                     q.push({nbr,1});
        //                     color[nbr]=1;
        //                 }
        //                 else{

        //                   color[nbr]=colorofnode+1;
        //                   q.push({nbr,colorofnode+1});
        //                 }

        //                 cout<<nbr<<" "<<color[nbr]<<endl;
        //             }
        //             else{
        //                 if(color[nbr]==colorofnode)
        //                 {
        //                     cout<<"hello"<<endl;
                            
        //                 }

        //             }
        //         }

        //         cout<<endl;
        //         cout<<endl;
        //     }
        // }

        // vector<int>ans;
        // for(int i=1;i<color.size();i++)
        // {
        //     ans.push_back(color[i]);
        // }

        // return ans;
        
    }
};
73905