//void __(){
//    _(int,n);
//    vvi adj(n+1);
//    rep(i,n-1){
//        _(int,u);
//        _(int,v);
//        adj[u].pb(v);
//        adj[v].pb(u);
//    }
//    vi side(n+1);
//    side[1] = 1;
//    vi bfs(1,1);
//    rep(i,sz(bfs)){
//        int u = bfs[i];
//        for(int v : adj[u])
//            if(side[v] == 0){
//                side[v] = side[u] * -1;
//                bfs.pb(v);
//            }
//    }
//    vi ls,rs;
//    vvi by_mod(3);
//    rep(u,1,n){
//        if(side[u] == -1)
//            ls.pb(u);
//        else
//            rs.pb(u);
//        by_mod[u%3].pb(u);
//    }
//    if(sz(ls) > sz(rs))
//        swap(ls,rs);
//    vi ans(n+1);
//    vi vec;
//    int l = 0;
//    if(sz(by_mod[0]) >= sz(ls)){
//        vec.insert(vec.end(),all(by_mod[0]));
//        vec.insert(vec.end(),all(by_mod[1]));
//        vec.insert(vec.end(),all(by_mod[2]));
//        for(int v : ls) ans[v] = vec[l++];
//        for(int v : rs) ans[v] = vec[l++];
//
//    }else if(sz(by_mod[1])+sz(by_mod[0]) >= sz(rs) && sz(rs) >= sz(by_mod[1])){
//        vec.insert(vec.end(),all(by_mod[1]));
//        vec.insert(vec.end(),all(by_mod[0]));
//        vec.insert(vec.end(),all(by_mod[2]));
//        for(int v : rs) ans[v] = vec[l++];
//        for(int v : ls) ans[v] = vec[l++];
//    }else{
//        assert(false);
//    }
//    ans.erase(ans.begin());
//    print ans;
//}
//
#include <iomanip>
#include <cassert>
#include <vector>
#include <utility>
#include <iostream>
#include <string>
#define pb push_back
#define REP_INT(i,l,r) for(int i = l; i <= r; ++i)
#define REP_ZERO_INT(i,r) for(int i = 0; i < r; ++i)
#define GET_REP_MACRO(_1,_2,_3,_4,NAME,...) NAME
#define rep(...) GET_REP_MACRO(__VA_ARGS__,REP_ANY,REP_INT,REP_ZERO_INT)(__VA_ARGS__)
#define all(v) (v).begin(), (v).end()
#define sz(v) ll(v.size())
#define T1 template<typename T> static
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
T1 ostream& operator<<(ostream& stream, const vector<T>& t);
T1 istream& read(T, T, istream& = cin);
struct _print {
    string sep,end;
    bool space;
    ostream &stream;
    _print(string _sep=" ",string _end="\n",
            ostream &_stream = cout)
        : sep(_sep),end(_end),space(false),
            stream(_stream) {}
    ~_print() { stream << end; }
    template <typename T>
        _print &operator , (const T &t) {
            if (space) stream << sep;
            space = true;
            stream << t;
            return *this;
        }
};
#define print _print(),
T1 ostream& operator<<(ostream& stream, const vector<T>& t){
    for(int i = 0; i < sz(t); ++i){
        stream << t[i];
        if(i+1 < sz(t))
            stream << ' ';
    }
    return stream;
}
#define INPUT_WITHOUT_INIT(type,name) type name; cin >> name
#define GET_INPUT_MACRO(_1,_2,_3,_4,_5,_6,_7,_8,NAME,...) NAME
#define _(...) GET_INPUT_MACRO(__VA_ARGS__,_IWI,_IWI,_IWI,_IWI,_IWI,_IWI,INPUT_WITHOUT_INIT)(__VA_ARGS__)
void __(){
    _(int,n);
    vvi adj(n+1);
    rep(i,n-1){
        _(int,u);
        _(int,v);
        adj[u].pb(v);
        adj[v].pb(u);
    }
    vi side(n+1);
    side[1] = 1;
    vi bfs(1,1);
    rep(i,sz(bfs)){
        int u = bfs[i];
        for(int v : adj[u])
            if(side[v] == 0){
                side[v] = side[u] * -1;
                bfs.pb(v);
            }
    }
    vi ls,rs;
    vvi by_mod(3);
    rep(u,1,n){
        if(side[u] == -1)
            ls.pb(u);
        else
            rs.pb(u);
        by_mod[u%3].pb(u);
    }
    if(sz(ls) > sz(rs))
        swap(ls,rs);
    vi ans(n+1);
    vi vec;
    int l = 0;
    if(sz(by_mod[0]) >= sz(ls)){
        vec.insert(vec.end(),all(by_mod[0]));
        vec.insert(vec.end(),all(by_mod[1]));
        vec.insert(vec.end(),all(by_mod[2]));
        for(int v : ls) ans[v] = vec[l++];
        for(int v : rs) ans[v] = vec[l++];
    }else if(sz(by_mod[1])+sz(by_mod[0]) >= sz(rs) && sz(rs) >= sz(by_mod[1])){
        vec.insert(vec.end(),all(by_mod[1]));
        vec.insert(vec.end(),all(by_mod[0]));
        vec.insert(vec.end(),all(by_mod[2]));
        for(int v : rs) ans[v] = vec[l++];
        for(int v : ls) ans[v] = vec[l++];
    }else{
        assert(false);
    }
    ans.erase(ans.begin());
    print ans;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);
        __();
}


Measured memory_bytes: 19568