/*
回答(https://img.atcoder.jp/hitachi2020/editorial.pdf)

命題の否定を考える
「 pi と pj の和または積が 3 の倍数である」という条件の否定は
「pi,pj を 3 で割ったあまりがと もに 1 である、または、pi,pj を 3 で割ったあまりがともに 2 である」です。
*/

#include<iostream>
#include<vector>
#include<string>
#include<queue>

std::vector<std::vector<std::pair<int, int> > > makeadjlist(int N){
    std::vector<std::vector<std::pair<int, int> > > adjlist(N);
    int a, b;

    for(int i=0; i<N-1; i++){
        std::cin >> a >> b;
        a = a-1; b = b-1;
        adjlist[a].push_back(std::make_pair(b,1));
        adjlist[b].push_back(std::make_pair(a,1));
    }
    return adjlist;
}

//重み付き無向グラフの場合
// start:開始点, vertexnum:頂点数, adjlist:隣接リスト<頂点番号, コスト>
std::vector<int> dijkstra(int start, int vertexnum, std::vector<std::vector<std::pair<int,int> > > adjlist){
    std::priority_queue<std::pair<int, int> > wait;
    std::vector<int> result(vertexnum, 1e9);

    result[start] = 0;
    wait.push(std::make_pair(start, 0));

    while(!wait.empty()){
        int nowpoint = wait.top().first;
        int nowcost = -wait.top().second;
        wait.pop();

        if(result[nowpoint] < nowcost){
            continue;
        }

        for(int i=0; i<adjlist[nowpoint].size(); i++){
            int nextpoint = adjlist[nowpoint][i].first;
            int nextcost = nowcost + adjlist[nowpoint][i].second;

            if(nextcost < result[nextpoint]){
                result[nextpoint] = nextcost;
                wait.push(std::make_pair(nextpoint, -nextcost));
            }
        }


    }

    return result;
}
std::vector<int> assignnum(std::string colored[], int vernum, int blue, int red){
    std::vector<int> sequence(vernum, 0);

    int remainder[3]={3,1,2};
    if(red <= vernum/3){
        for(int i=0; i<vernum; i++){
            if(colored[i].compare("red") == 0){
                sequence[i] = remainder[0];
                remainder[0] += 3;
            }else if(colored[i].compare("blue") == 0){
                if(remainder[1] <= vernum){
                    sequence[i] = remainder[1];
                    remainder[1] += 3;
                }else if(remainder[2] <= vernum){
                    sequence[i] = remainder[2];
                    remainder[2] += 3;
                }else{
                    sequence[i] = remainder[0];
                    remainder[0] += 3;
                }
            }
        }
    }else if(blue <= vernum/3){
        for(int i=0; i<vernum; i++){
            if(colored[i].compare("blue") == 0){
                sequence[i] = remainder[0];
                remainder[0] += 3;
            }else if(colored[i].compare("red") == 0){
                if(remainder[1] <= vernum){
                    sequence[i] = remainder[1];
                    remainder[1] += 3;
                }else if(remainder[2] <= vernum){
                    sequence[i] = remainder[2];
                    remainder[2] += 3;
                }else{
                    sequence[i] = remainder[0];
                    remainder[0] += 3;
                }
            }
        }
    }else if(red > vernum/3 && blue > vernum/3){
        for(int i=0; i<vernum; i++){
            if(colored[i].compare("red") == 0){
                if(remainder[1] <= vernum){
                    sequence[i] = remainder[1];
                    remainder[1] += 3;
                }else{
                    sequence[i] = remainder[0];
                    remainder[0] += 3;
                }

            }else if(colored[i].compare("blue") == 0){
                if(remainder[2] <= vernum){
                    sequence[i] = remainder[2];
                    remainder[2] += 3;
                }else{
                    sequence[i] = remainder[0];
                    remainder[0] += 3;
                }
            }
        }
    }
    return sequence;
}

int main(void){
    int N;
    std::cin >> N;
    std::vector<std::vector<std::pair<int, int> > > adjlist(N);

    adjlist = makeadjlist(N);

    std::string colored[N];
    int red=0, blue=0;
    std::vector<int> result = dijkstra(1,N,adjlist);
    for(int i=0; i<result.size(); i++){
        if(result[i] % 2 == 0){
            colored[i] = "red";
            red += 1;
        }
        else {
            colored[i] = "blue";
            blue += 1;
        }
    }

    std::vector<int> ans =assignnum(colored, N, blue, red);

    for(int i=0; i<N; i++){
        std::cout << ans[i] << " ";
    }
    return 0;
}

Measured memory_bytes: 32076