//{{{
#include<algorithm>
#include<cmath>
#include<deque>
#include<fstream>
#include<iomanip>
#include<iostream>
#include<map>
#include<numeric>
#include<queue>
#include<random>
#include<set>
#include<sstream>
#include<sys/time.h>
#include<unordered_map>
#include<unordered_set>
#include<vector>
using ll = long long;
enum : int { M = (int)1e9 + 7 };
enum : ll { MLL = (ll)1e18L + 9 };
using namespace std;
#ifdef LOCAL
#include"rprint2.hpp"
#else
#define FUNC(name) template <ostream& out = cout, class... T> void name(T&&...){ }
FUNC(printde) FUNC(printdbe) FUNC(printdwe) FUNC(printdu);
#endif
template <template <class T, class = std::allocator<T>> class V, class E>
istream& operator >> (istream& in, V<E>& v){ for(auto& e : v){ in >> e; } return in; }
//}}}

struct Graph{
    struct Node{
        vector<int> dests;
        int color = -1;
    };
    vector<Node> nodes;
    Graph(int num): nodes(num){ }
    int id(Node* n){ return n - &nodes[0]; }
    int id(Node& n){ return &n - &nodes[0]; }
    // void print(){ for(auto& node : nodes){ prints(id(node), node.dests); } }
    void add1Edge(int from, int dest){
        nodes[from].dests.push_back(dest);
    }
    void add2Edge2(int from, int dest){
        add1Edge(from, dest);
        add1Edge(dest, from);
    }
    void dfs(int idx, int c, int from = -1){
        nodes[idx].color = c;
        for(int didx : nodes[idx].dests){
            if(didx == from){ continue; }
            dfs(didx, !c, idx);
        }
    }
};

int main(){
    cin.tie(0); ios::sync_with_stdio(false);
    int n; cin >> n;
    Graph g(n);
    for(int i = 0; i < n - 1; i++){
        int a, b;
        cin >> a >> b;
        a--; b--;
        g.add2Edge2(a, b);
    }
    g.dfs(0, 0);
    int c1 = 0, c0 = 0;
    for(int i = 0; i < n; i++){
        c1 += g.nodes[i].color == 1;
        c0 += g.nodes[i].color == 0;
    }
    bool rev = c0 > c1;
    int one = n / 3 + (n % 3 != 0);
    int two = n / 3 + (n % 3 == 2);
    int three = 0;
    stringstream ss;
    if(min(c1, c0) <= n / 3){
        if(c1 < c0){
            for(int i = 0; i < n; i++){
                if((three + 1) * 3 <= n && (g.nodes[i].color)){
                    three++;
                    ss << three * 3 << ' ';
                }else if(two && (!g.nodes[i].color)){
                    two--;
                    ss << two * 3 + 2 << ' ';
                }else{
                    if(one){
                        one--;
                        ss << one * 3 + 1 << ' ';
                    }else if((three + 1) * 3 <= n){
                        three++;
                        ss << three * 3 << ' ';
                    }else{
                        two--;
                        ss << two * 3 + 2 << ' ';
                    }
                }
            }
        }else{
            for(int i = 0; i < n; i++){
                if(one && (g.nodes[i].color)){
                    one--;
                    ss << one * 3 + 1 << ' ';
                }else if((three + 1) * 3 <= n && (!g.nodes[i].color)){
                    three++;
                    ss << three * 3 << ' ';
                }else{
                    if(two){
                        two--;
                        ss << two * 3 + 2 << ' ';
                    }else if((three + 1) * 3 <= n){
                        three++;
                        ss << three * 3 << ' ';
                    }else{
                        one--;
                        ss << one * 3 + 1 << ' ';
                    }
                }
            }
        }
        cout << ss.str() << '\n';
        return 0;
    }
    // printde(one, two);
    // printde(c1, c0);
    // for(int i = 0; i < n; i++){
    //     if(one && (g.nodes[i].color ^ rev)){
    //         one--;
    //         ss << one * 3 + 1 << ' ';
    //     }else if(two && (!g.nodes[i].color ^ rev)){
    //         two--;
    //         ss << two * 3 + 2 << ' ';
    //     }else{
    //         three++;
    //         if(three * 3 > n){
    //             if(one){
    //                 one--;
    //                 ss << one * 3 + 1 << ' ';
    //             }else{
    //                 two--;
    //                 ss << two * 3 + 2 << ' ';
    //             }
    //             // cout << -1 << '\n';
    //             // return 0;
    //         }else{
    //             ss << three * 3 << ' ';
    //         }
    //     }
    //     return 0;
    // }
    printde(one, two);
    printde(c1, c0);
    // stringstream ss;
    for(int i = 0; i < n; i++){
        if(one && (g.nodes[i].color ^ rev)){
            one--;
            ss << one * 3 + 1 << ' ';
        }else if(two && (!g.nodes[i].color ^ rev)){
            two--;
            ss << two * 3 + 2 << ' ';
        }else{
            three++;
            if(three * 3 > n){
                if(one){
                    one--;
                    ss << one * 3 + 1 << ' ';
                }else{
                    two--;
                    ss << two * 3 + 2 << ' ';
                }
                // cout << -1 << '\n';
                // return 0;
            }else{
                ss << three * 3 << ' ';
            }
        }
    }
    cout << ss.str() << '\n';
}


Measured memory_bytes: 22900