#include <iostream>
#include <vector>
#include <functional>
#include <algorithm>
using namespace std;

int main()
{
    int N;
    cin>>N;
    vector<vector<int>> E(N);
    for (int i=0; i<N-1; i++)
    {
        int a, b;
        cin>>a>>b;
        E[a-1].push_back(b-1);
        E[b-1].push_back(a-1);
    }

    vector<int> D(N);
    function<void(int, int, int)> f = [&](int c, int p, int d)
    {
        D[c] = d;
        for (int e: E[c])
            if (e!=p)
                f(e, c, d+1);
    };
    f(0, -1, 0);

    vector<int> VE;
    vector<int> VO;
    for (int i=0; i<N; i++)
        (D[i]%2==0 ? VE : VO).push_back(i);
    int n1 = N/3+int(N%3==1 || N%3==2);
    int n2 = N/3+int(N%3==2);
    int n0 = N/3;
    vector<int> p(N);

    if (VE.size()<VO.size())
    {
        if (n2<=(int)VE.size())
        {
            for (int i=1; i<=N; i++)
                if (i%3==2)
                {
                    p[VE.back()] = i;
                    VE.pop_back();
                }
                else if (i%3==1)
                {
                    p[VO.back()] = i;
                    VO.pop_back();
                }
            for (int i=1; i<=N; i++)
                if (i%3==0)
                    if (!VE.empty())
                    {
                        p[VE.back()] = i;
                        VE.pop_back();
                    }
                    else
                    {
                        p[VO.back()] = i;
                        VO.pop_back();
                    }
        }
        else if ((int)VE.size()<=n0)
        {
            for (int i=1; i<=N; i++)
                if (i%3==0)
                    if (!VE.empty())
                    {
                        p[VE.back()] = i;
                        VE.pop_back();
                    }
                    else
                    {
                        p[VO.back()] = i;
                        VO.pop_back();
                    }
            for (int i=1; i<=N; i++)
                if (i%3!=0)
                {
                    p[VO.back()] = i;
                    VO.pop_back();
                }            
        }
        else
        {
            cout<<-1<<endl;
            return 0;
        }
    }
    else
    {
        if (n2<=(int)VO.size())
        {
            for (int i=1; i<=N; i++)
                if (i%3==2)
                {
                    p[VO.back()] = i;
                    VO.pop_back();
                }
                else if (i%3==1)
                {
                    p[VE.back()] = i;
                    VE.pop_back();
                }
            for (int i=1; i<=N; i++)
                if (i%3==0)
                    if (!VE.empty())
                    {
                        p[VE.back()] = i;
                        VE.pop_back();
                    }
                    else
                    {
                        p[VO.back()] = i;
                        VO.pop_back();
                    }
        }
        else if ((int)VO.size()<=n0)
        {
            for (int i=1; i<=N; i++)
                if (i%3==0)
                    if (!VO.empty())
                    {
                        p[VO.back()] = i;
                        VO.pop_back();
                    }
                    else
                    {
                        p[VE.back()] = i;
                        VE.pop_back();
                    }
            for (int i=1; i<=N; i++)
                if (i%3!=0)
                {
                    p[VE.back()] = i;
                    VE.pop_back();
                }            
        }
        else
        {
            cout<<-1<<endl;
            return 0;
        }
    }
    for (int t: p)
        cout<<t<<endl;
}


Measured memory_bytes: 23540