Language: C++

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,tot,rt,d[N],ans[N],sa,sb,f[N][2],g[N][2],head[N],nex[N<<1],to[N<<1];
void add(int u,int v){to[++tot]=v;nex[tot]=head[u];head[u]=tot;}
vector<int>v[3];
int get(int x)
{
    int ans=v[x].back();v[x].pop_back();return ans;
}
void dfs1(int u,int fa)
{
    f[u][0]=1;
    for(int i=head[u];i;i=nex[i])
    {
        int v=to[i];if(v==fa) continue;
        dfs1(v,u);
        f[u][0]+=f[v][1];
        f[u][1]+=f[v][0];
    }
}
void dfs2(int u,int fa)
{
    if(f[u][0]>=v[1].size()&&f[u][1]>=v[2].size()||f[u][0]>=v[2].size()&&f[u][1]>=v[1].size())
        rt=u,sa=f[u][0],sb=f[u][1];
    g[u][0]=f[u][0];g[u][1]=f[u][1];
    for(int i=head[u];i;i=nex[i])
    {
        int v=to[i];if(v==fa) continue;
        f[u][0]-=f[v][1];
        f[u][1]-=f[v][0];
        f[v][0]+=f[u][1];
        f[v][1]+=f[u][0];
        dfs2(v,u);
        f[v][0]-=f[u][1];
        f[v][1]-=f[u][0];
        f[u][0]+=f[v][1];
        f[u][1]+=f[v][0];
    }
}
int k;
void dfs(int u,int fa,int dep)
{
    if(dep==k)
    {
        if(v[1].size())
            ans[u]=v[1].back(),v[1].pop_back();
        else  if(v[0].size()) ans[u]=v[0].back(),v[0].pop_back();
        else
        {
            printf("-1\n");exit(0);
        }
    }
    else
    {
        if(v[2].size())
            ans[u]=v[2].back(),v[2].pop_back();
        else  if(v[0].size()) ans[u]=v[0].back(),v[0].pop_back();
        else
        {
            printf("-1\n");exit(0);
        }
    }
    for(int i=head[u];i;i=nex[i])
    {
        int v=to[i];if(v==fa) continue;
        dfs(v,u,dep^1);
    }
}
int p[N];
void Add(int u,int s)
{
    if(s==k)
    {
        if(v[1].size())
            ans[u]=get(1);
        else ans[u]=get(0);
    }
    else
    {
        if(v[2].size())
            ans[u]=get(2);
        else ans[u]=get(0);
    }
}
void solve(int u,int fa,int dep)
{
    if(dep==1)
    {
        if(d[u]!=1)
        {
            Add(u,dep&1);
        }
    }
    else if(dep==2)
    {
        ans[u]=get(0);
    }
    else
    {
        Add(u,dep&1);
    }
    for(int i=head[u];i;i=nex[i])
    {
        int v=to[i];if(v==fa) continue;
        solve(v,u,dep+1);
    }
}
void solve(int rt)
{
    if(g[rt][0]<=v[1].size()&&g[rt][1]<=v[2].size()) k=0;
    else k=1;
    int s=v[0].size()-p[rt];
    if(g[rt][0]<=v[1].size()+s&&g[rt][1]<=v[2].size()+s-max(g[rt][0]-(int)v[1].size(),0)) k=0;
    else k=1;
    solve(rt,0,0);
    for(int i=1;i<=n;i++)
    {
        if(!ans[i])
        {
            if(v[0].size()) ans[i]=get(0);
            else if(v[1].size()) ans[i]=get(1);
            else ans[i]=get(2);
        }
        printf(i==n?"%d\n":"%d ",ans[i]);
    }
}
int f[N];
bool cmp(int x,int y)
{
    return d[x]>d[y];
}
void dfs(int u,int dep)
{
    if(!ans[u])
    {
        if(dep) ans[u]=-1;
        else ans[u]==-2;
    }
    for(int i=head[u];i;i=nex[i])
        if(!ans[to[i]]) dfs(to[i],dep^1);
}
void solve3()
{
    for(int i=1;i<=n;i++)
        f[i]=i;
    sort(f+1,f+1+n,cmp);
    for(int i=1;i<=n;i++)
    {
        if(v[0].size())
        {
            ans[f[i]]=get(0);
        }
        else break;
    }
    dfs(1,0);
    int s=0,t=0;
    for(int i=1;i<=n;i++)
        if(ans[i]==-1) s++;
    else if(ans[i]==-2) t++;
    int k;
    if(s>=t&&v[1].size()>=v[2].size()) k=-1;
    else k=-2;
    for(int i=1;i<=n;i++)
    {
        if(ans[i]<0)
        {
            if(ans[i]==k&&v[1].size()) ans[i]=get(1);
            else ans[i]=get(2);
        }
        printf(i==n?"%d\n":"%d ",ans[i]);
    }
}
void solve()
{
    for(int i=1;i<=n;i++)
    {
        for(int j=head[i];j;j=nex[j])
        {
            int v=to[j];
            if(d[v]==1) g[i][1]--;
            g[i][0]-=d[v]-1,p[i]+=d[v]-1;
        }
        if(p[i]>v[0].size()) continue;
        int s=v[0].size()-p[i];
        if(g[i][0]<=v[1].size()&&g[i][1]<=v[2].size()||g[i][1]<=v[1].size()&&g[i][0]<=v[2].size())
        {
            solve(i);exit(0);
        }
        if(g[i][0]<=v[1].size()+s&&g[i][1]<=v[2].size()+s-max(g[i][0]-(int)v[1].size(),0)||g[i][1]<=v[1].size()+s&&g[i][0]<=v[2].size()+s-max(g[i][1]-(int)v[1].size(),0))
        {
            solve(i);exit(0);
        }
    }
    solve3();
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        v[i%3].push_back(i);
    for(int i=1;i<n;i++)
    {
        int u,v;scanf("%d%d",&u,&v);add(u,v);add(v,u);
        d[u]++;d[v]++;
    }
    dfs1(1,0);
    dfs2(1,0);
    if(rt==0)
    {
        solve();
        return 0;
    }
    if(sa>=v[1].size()&&sb>=v[2].size()) k=0;
    else k=1;
    dfs(rt,0,0);
    for(int i=1;i<=n;i++)
        printf(i==n?"%d\n":"%d ",ans[i]);
}


Compiler output:
a.cc:128:5: error: conflicting declaration 'int f [200005]'
  128 | int f[N];
      |     ^
a.cc:4:32: note: previous declaration as 'int f [200005][2]'
    4 | int n,tot,rt,d[N],ans[N],sa,sb,f[N][2],g[N][2],head[N],nex[N<<1],to[N<<1];
      |                                ^
a.cc: In function 'void solve3()':
a.cc:146:13: error: incompatible types in assignment of 'int' to 'int [2]'
  146 |         f[i]=i;
      |         ~~~~^~
a.cc:152:16: error: invalid types 'int [200005][int [2]]' for array subscript
  152 |             ans[f[i]]=get(0);
      |                ^
In file included from /usr/include/c++/14/algorithm:61,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:51,
                 from a.cc:1:
/usr/include/c++/14/bits/stl_algo.h: In instantiation of 'void std::__insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = int (*)[2]; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(int, int)>]':
/usr/include/c++/14/bits/stl_algo.h:1817:25:   required from 'void std::__final_insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = int (*)[2]; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(int, int)>]'
 1817 |           std::__insertion_sort(__first, __first + int(_S_threshold), __comp);
      |           ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:1908:31:   required from 'void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = int (*)[2]; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(int, int)>]'
 1908 |           std::__final_insertion_sort(__first, __last, __comp);
      |           ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:4805:18:   required from 'void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = int (*)[2]; _Compare = bool (*)(int, int)]'
 4805 |       std::__sort(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
      |       ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:147:9:   required from here
  147 |     sort(f+1,f+1+n,cmp);
      |     ~~~~^~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:1780:17: error: array must be initialized with a brace-enclosed initializer
 1780 |                 __val = _GLIBCXX_MOVE(*__i);
      |                 ^~~~~
/usr/include/c++/14/bits/stl_algo.h:1782:24: error: invalid array assignment
 1782 |               *__first = _GLIBCXX_MOVE(__val);
      |                        ^
In file included from /usr/include/c++/14/bits/stl_algobase.h:71,
                 from /usr/include/c++/14/algorithm:60:
/usr/include/c++/14/bits/predefined_ops.h: In instantiation of 'constexpr bool __gnu_cxx::__ops::_Iter_comp_iter<_Compare>::operator()(_Iterator1, _Iterator2) [with _Iterator1 = int (*)[2]; _Iterator2 = int (*)[2]; _Compare = bool (*)(int, int)]':
/usr/include/c++/14/bits/stl_algo.h:1777:14:   required from 'void std::__insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = int (*)[2]; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(int, int)>]'
 1777 |           if (__comp(__i, __first))
      |               ~~~~~~^~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:1817:25:   required from 'void std::__final_insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = int (*)[2]; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(int, int)>]'
 1817 |           std::__insertion_sort(__first, __first + int(_S_threshold), __comp);
      |           ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:1908:31:   required from 'void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = int (*)[2]; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(int, int)>]'
 1908 |           std::__final_insertion_sort(__first, __last, __comp);
      |           ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:4805:18:   required from 'void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = int (*)[2]; _Compare = bool (*)(int, int)]'
 4805 |       std::__sort(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
      |       ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:147:9:   required from here
  147 |     sort(f+1,f+1+n,cmp);
      |     ~~~~^~~~~~~~~~~~~~~
/usr/include/c++/14/bits/predefined_ops.h:158:32: error: invalid conversion from 'int*' to 'int' [-fpermissive]
  158 |         { return bool(_M_comp(*__it1, *__it2)); }
      |                                ^~~~~
      |                                |
      |                                int*
/usr/include/c++/14/bits/predefined_ops.h:158:40: error: invalid conversion from 'int*' to 'int' [-fpermissive]
  158 |         { return bool(_M_comp(*__it1, *__it2)); }
      |                                        ^~~~~
      |                                        |
      |                                        int*
In file included from /usr/include/c++/14/bits/stl_algo.h:61:
/usr/include/c++/14/bits/stl_heap.h: In instantiation of 'void std::__make_heap(_RandomAccessIterator, _RandomAccessIterator, _Compare&) [with _RandomAccessIterator = int (*)[2]; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(int, int)>]':
/usr/include/c++/14/bits/stl_algo.h:1593:23:   required from 'void std::__heap_select(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = int (*)[2]; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(int, int)>]'
 1593 |       std::__make_heap(__first, __middle, __comp);
      |       ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:1868:25:   required from 'void std::__partial_sort(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = int (*)[2]; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(int, int)>]'
 1868 |       std::__heap_select(__first, __middle, __last, __comp);
      |       ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:1884:27:   required from 'void std::__introsort_loop(_RandomAccessIterator, _RandomAccessIterator, _Size, _Compare) [with _RandomAccessIterator = int (*)[2]; _Size = long int; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(int, int)>]'
 1884 |               std::__partial_sort(__first, __last, __last, __comp);
      |               ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:1905:25:   required from 'void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = int (*)[2]; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(int, int)>]'
 1905 |           std::__introsort_loop(__first, __last,
      |           ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
 1906 |                                 std::__lg(__last - __first) * 2,
      |                                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 1907 |                                 __comp);
      |                                 ~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:4805:18:   required from 'void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = int (*)[2]; _Compare = bool (*)(int, int)]'
 4805 |       std::__sort(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
      |       ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:147:9:   required from here
  147 |     sort(f+1,f+1+n,cmp);
      |     ~~~~^~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_heap.h:355:22: error: array must be initialized with a brace-enclosed initializer
  355 |           _ValueType __value = _GLIBCXX_MOVE(*(__first + __parent));
      |                      ^~~~~~~
/usr/include/c++/14/bits/stl_heap.h: In instantiation of 'void std::__pop_heap(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, _Compare&) [with _RandomAccessIterator = int (*)[2]; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(int, int)>]':
/usr/include/c++/14/bits/stl_algo.h:1596:19:   required from 'void std::__heap_select(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = int (*)[2]; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(int, int)>]'
 1596 |           std::__pop_heap(__first, __middle, __i, __comp);
      |           ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:1868:25:   required from 'void std::__partial_sort(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = int (*)[2]; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(int, int)>]'
 1868 |       std::__heap_select(__first, __middle, __last, __comp);
      |       ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:1884:27:   required from 'void std::__introsort_loop(_RandomAccessIterator, _RandomAccessIterator, _Size, _Compare) [with _RandomAccessIterator = int (*)[2]; _Size = long int; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(int, int)>]'
 1884 |               std::__partial_sort(__first, __last, __last, __comp);
      |               ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:1905:25:   required from 'void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = int (*)[2]; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(int, int)>]'
 1905 |           std::__introsort_loop(__first, __last,
      |           ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
 1906 |                                 std::__lg(__last - __first) * 2,
      |                                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 1907 |                                 __comp);
      |                                 ~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:4805:18:   required from 'void std::sort(_RAIter, _RAIter, _Compare) [with _RAIt