#include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int mod=1e9+7;
int tmp[200000];
vector<int>G[200000];
void dfs(int v){
    for(int i=0;i<G[v].size();i++){
        if(tmp[G[v][i]]==0){
            tmp[G[v][i]]=-tmp[v];
            dfs(G[v][i]);
        }
    }
}
signed main(){
    int n,a,b;
    cin>>n;
    for(int i=0;i<n-1;i++){
        cin>>a>>b;
        a--,b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    tmp[0]=1;
    dfs(0);
    vector<int>odd,even;
    for(int i=0;i<n;i++)
        if(tmp[i]==1)
            odd.push_back(i);
        else
            even.push_back(i);
    int ans[200000];
    vector<int>odd2,even2;
    if(odd.size()<=n/3)
        for(int i=1;i<=n;i++)
            (i%3==0&&i/3<=odd.size()?odd2:even2).push_back(i);
    else if(even.size()<=n/3)
        for(int i=1;i<=n;i++)
            (i%3==0&&i/3<=even.size()?even2:odd2).push_back(i);
    else
        for(int i=1;i<=n;i++)
            (i%3==1||i%3==0&&i/3<=odd.size()-(n+2)/3?odd2:even2).push_back(i);
    for(int i=0;i<odd.size();i++)
        ans[odd[i]]=odd2[i];
    for(int i=0;i<even.size();i++)
        ans[even[i]]=even2[i];
    for(int i=0;i<n;i++)
        cout<<ans[i]<<(i+1==n?'\n':' ');
}
