#include <bits/stdc++.h>
using namespace std;
 
#define REP(i, s) for (int i = 0; i < s; ++i)
#define ALL(v) (v).begin(), (v).end()
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
#define EACH(i, s) for (__typeof__((s).begin()) i = (s).begin(); i != (s).end(); ++i)
#define DEBUG
#define int long long
#define INF 1e18
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }
template<class T> ostream& operator << (ostream &s, set<T> P)
{ EACH(it, P) { s << "<" << *it << "> "; } return s << endl; }
template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> P)
{ EACH(it, P) { s << "<" << it->first << "->" << it->second << "> "; } return s << endl; }
template<class T>void show(vector<T>v){for (int i = 0; i < v.size(); i++){cerr<<v[i]<<" ";}cerr<<"\n";}
typedef long long ll;

using Graph=vector<vector<int>>;
Graph G;
vector<int>d;

void dfs(int v, int p){
    for(auto & nv : G[v]){
        if (nv==p) continue;
        d[nv]=d[v]+1;
        dfs(nv,v);
    }
}

signed main()
{
    int n;
    cin>>n;
    vector<int>a(n-1),b(n-1);
    vector<int>p(n);
    d.resize(n);
    G.assign(n,vector<int>());
    REP(i,n-1) {
        cin>>a[i]>>b[i];
        a[i]--,b[i]--;
        G[a[i]].push_back(b[i]);
        G[b[i]].push_back(a[i]);
    }
    dfs(0,-1);
    vector<bool>c(n,false);
    int cnt=0;
    for (int i = 0; i < n; i++)
    {
        if(d[i]%2==0) {
            c[i]=true;
            cnt++;
        }
    }
    int even=cnt;
    int odd=n-cnt;
    if(even > n/3 && odd > n/3){
        int cnt1=1,cnt2=2;
        int index1,index2;
        for (int i = 0; i < n; i++)
        {
            if(d[i]%2==0) {
                p[i]=cnt1;
                cnt1+=3;
                if(cnt1>n) {
                    index1=i+1;
                    break;
                }
            }
        }
        for (int i = 0; i < n; i++)
        {
            if(d[i]%2==1){
                p[i]=cnt2;
                cnt2+=3;
                if(cnt2>n) {
                    index2=i+1;
                    break;
                }
            }
        }
        int x=3;
        for (int i = index1; i < n; i++)
        {
            if(d[i]%2==0){
                p[i] = x;
                x+=3;
            }
        }
        int y=x;
        for (int i = index2; i < n; i++)
        {
            if(d[i]%2==1){
                p[i]=y;
                y+=3;
            }
        }    
    }
    else if( even <= n/3 ){
        int s=3;
        for (int i = 0; i < n; i++)
        {
            if(d[i]%2==0){
                p[i]=s;
                s+=3;
            }
        }
        int index1 = 0;
        if(s<=n){
        for (int i = 0; i < n; i++)
        {
            if(d[i]%2==1){
                p[i]=s;
                s+=3;
                if(s>n){
                    index1=i+1;
                    break;
                }
            }
        }
        }
        int t=1;
        for (int i = index1; i < n; i++)
        {
            if(d[i]%2==1){
                p[i]=t;
                t++;
                if(t%3==0) t++;
            }
        }
        
    }
    else{
        int s = 3;
        for (int i = 0; i < n; i++)
        {
            if (d[i] % 2 == 1)
            {
                p[i] = s;
                s += 3;
            }
        }
        int index1 = 0;
        if(s<=n){
        for (int i = 0; i < n; i++)
        {
            if (d[i] % 2 == 0)
            {
                p[i] = s;
                s += 3;
                if (s > n)
                {
                    index1 = i + 1;
                    break;
                }
            }
        }
        }
        int t = 1;
        for (int i = index1; i < n; i++)
        {
            if (d[i] % 2 == 0)
            {
                p[i] = t;
                t++;
                if (t % 3 == 0)
                    t++;
            }
        }
    }

    for (int i = 0; i < n; i++)
    {
        cout<<p[i]<<" ";
    }
    cout<<endl;
    return 0;
}

Measured memory_bytes: 21504