Codeforces 1627C - Not Assigning Solution

///******Bismillahir-Rahmanir-Rahim******///

///AH Tonmoy

///Department of CSE,23rd batch

///Islamic University,Bangladesh

#include <bits/stdc++.h>

using namespace std;

#define mx 100005

vector<int>g[mx],gind[mx];

int ans[mx],vis[mx],i;

void clean(int n)

{

    for(i=0; i<=n; i++)

    {

        g[i].clear();

        gind[i].clear();

        ans[i]=0;

        vis[i]=0;

    }

}

void dfs(int src,int prime)

{

    vis[src]=1;

    for(i=0; i<g[src].size(); i++)

    {

        int next=g[src][i];

        if(vis[next]==1)

            continue;

        int indp=gind[src][i];

        ans[indp]=prime;

        dfs(next,5-prime);

    }

}

int main()

{

    ios::sync_with_stdio(false);

    cin.tie(0);

    int t,n,i,invalid;

    cin>>t;

    while(t--)

    {

        invalid=0;

        int u,v,node,s;

        cin>>node;

        clean(node);

        for(i=1; i<node; i++)

        {

            cin>>u>>v;

            g[u].push_back(v);

            g[v].push_back(u);

            gind[u].push_back(i);

            gind[v].push_back(i);

        }

        for(i=1; i<=node; i++)

        {

            if(g[i].size()==1)

            {

                s=i;

            }

            else  if(g[i].size()>2)

            {

                invalid=1;

                break;

            }

        }

        if(invalid==1)

        {

            cout<<"-1"<<endl;

            continue;

        }

        dfs(s,2);

        for(i=1; i<node; i++)

        {

            cout<<ans[i]<<" ";

        }

        cout<<endl;

    }

}