#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<bitset>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<deque>
#include<list>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<functional>
using namespace std;

#define repr(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) repr(i, 0, n)
#define INF 2e9
#define MOD 1000000007
//#define MOD 998244353
#define LINF (long long)4e18
#define jck 3.141592

using ll = long long;
using Pi = pair<int,int>;
using Pl = pair<ll,ll>;

class DisjointSet{
    public:
        vector<ll> rank,p,siz;

        DisjointSet(){}
        DisjointSet(ll size){
            rank.resize(size,0);
            p.resize(size,0);
            siz.resize(size,1);
            rep(i,size) makeSet(i);
        }

        void makeSet(ll x){
            p[x] = x;
            rank[x] = 0;
        }

        bool same(ll x, ll y){
            return root(x) == root(y);
        }

    
        void unite(ll x, ll y){
            x = root(x);
            y = root(y);
            if(rank[x] > rank[y]){
                siz[x] += siz[y];
                p[y] = x;
            }
            else{
                siz[y] += siz[x];
                p[x] = y;
                if(rank[x] == rank[y]) rank[y]++;
            } 
        }
        ll root(ll x){
            if(x != p[x]){
                p[x] = root(p[x]);
            }
            return p[x];
        }

        ll size(ll x){
            return siz[root(x)];
        }

};


int N;
vector<vector<int>> G;
DisjointSet uf(200010);
int now1 = 1,now2 = 2,now3 = 3;
vector<bool> ok;

void dfs(int u,int p,int depth){
    if(u != 0 && depth%2 == 0){
        uf.unite(u,0);
        ok[u] = true;
    }
    for(int v : G[u]){
        if(v == p) continue;
        dfs(v,u,depth+1);
    }
}

int main(){
    cin >> N;
    G.resize(N);  
    ok.resize(N,false);  
    ok[0] = true;
    rep(i,N-1){
        int a,b; cin >> a >> b;
        a--; b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    vector<int> ans(N,-1);
    dfs(0,-1,0);
    if(uf.size(0) >= N-N/3){
        rep(i,N){
            if(ok[i]){
                ans[i] = now1;
                now1 += 3;
                if(now1 > N) break;
            }
        }
        rep(i,N){
            if(ok[i] && ans[i] == -1){
                ans[i] = now2;
                now2 += 3;
                if(now2 > N) break;
            }
        }
        rep(i,N){
            if(ans[i] == -1){
                ans[i] = now3;
                now3 += 3;
            }
        }
        rep(i,N) cout << ans[i] << " ";
        cout << endl;
    }
    else if(uf.size(0) < N/3){
        rep(i,N){
            if(!ok[i]){
                ans[i] = now1;
                now1 += 3;
                if(now1 > N) break;
            }
        }
        rep(i,N){
            if(!ok[i] && ans[i] == -1){
                ans[i] = now2;
                now2 += 3;
                if(now2 > N) break;
            }
        }
        rep(i,N){
            if(ans[i] == -1){
                ans[i] = now3;
                now3 += 3;
            }
        }
        rep(i,N) cout << ans[i] << " ";
        cout << endl;
    }
    else{
        rep(i,N){
            if(ok[i]){
                ans[i] = now1;
                now1 += 3;
                if(now1 > N) break;
            }
        }
        rep(i,N){
            if(!ok[i]){
                ans[i] = now2;
                now2 += 3;
                if(now2 > N) break;
            }
        }
        rep(i,N){
            if(ans[i] == -1){
                ans[i] = now3;
                now3 += 3;
            }
        }
        rep(i,N) cout << ans[i] << " ";
        cout << endl;
    }
}

Measured memory_bytes: 41088