#include <bits/stdc++.h>

using namespace std;

template <class TH> void _dbg(const char *sdbg, TH h){cerr<<sdbg<<"="<<h<<"\n";}
template<class TH, class... TA> void _dbg(const char *sdbg, TH h, TA... a) {
  while(*sdbg!=',')
    cerr<<*sdbg++;
  cerr<<"="<<h<<","; 
  _dbg(sdbg+1, a...);
}

template<class T> ostream & operator<<(ostream & os, vector<T> V){
  os<<"[";
  for(auto vv: V) os << vv <<",";
  return os << "]";
}
template<class L, class R> ostream & operator <<(ostream & os, pair<L,R> P){
  return os <<"("<<P.first <<","<<P.second <<")";
}

#ifdef DEBUG
#define debug(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...) (__VA_ARGS__)
#define cerr if(0)cout
#endif

const int N = 200005;

int n, a, b;
vector<int> V[N];
int color[N];
int ans[N];
bool vis[N];
int cntColors[5];

int main() {
    
    scanf("%d", &n);
    
    for (int i = 2; i <= n; i++) {
        scanf("%d %d", &a, &b);
        V[a].push_back(b);
        V[b].push_back(a);
    }
    
    int firstOdd = 1;
    int firstEven = 2;
    int firstZero = 3;
    
    queue<int> Q;
    Q.push(1);
    vis[1] = true;
    
    while (!Q.empty()) {
        int w = Q.front();
        Q.pop();
        cntColors[color[w]]++;
        for (int u : V[w]) {
            if (vis[u]) continue;
            vis[u] = true;
            color[u] = 1 - color[w];
            Q.push(u);
        }
    }
    
    if (cntColors[0] <= n / 3) {
        for (int i = 1; i <= n; i++) {
            if (color[i] == 0) {
                ans[i] = firstZero;
                firstZero += 3;
            }
        }
        for (int i = 1; i <= n; i++) {
            if (color[i]) {
                if (firstEven <= n) {
                    ans[i] = firstEven;
                    firstEven += 3;
                } else if (firstOdd <= n) {
                    ans[i] = firstOdd;
                    firstOdd += 3;
                } else if (firstZero <= n) {
                    ans[i] = firstZero;
                    firstZero += 3;
                }
            }
        }
    } else if (cntColors[1] <= n / 3) {
        for (int i = 1; i <= n; i++) {
            if (color[i] == 1) {
                ans[i] = firstZero;
                firstZero += 3;
            }
        }
        for (int i = 1; i <= n; i++) {
            if (color[i] == 0) {
                if (firstEven <= n) {
                    ans[i] = firstEven;
                    firstEven += 3;
                } else if (firstOdd <= n) {
                    ans[i] = firstOdd;
                    firstOdd += 3;
                } else if (firstZero <= n) {
                    ans[i] = firstZero;
                    firstZero += 3;
                }
            }
        }
    } else {
        for (int i = 1; i <= n; i++) ans[i] = -1;
        for (int i = 1; i <= n; i++) {
            if (color[i] == 0 && cntColors[0] > (n + 2) / 3) {
                ans[i] = firstZero;
                firstZero += 3;
                cntColors[0]--;
                continue;
            }
            if (color[i] == 1 && cntColors[1] > (n + 1) / 3) {
                ans[i] = firstZero;
                firstZero += 3;
                cntColors[1]--;
                continue;
            }
        } 
        
        for (int i = 1; i <= n; i++) {
            if (ans[i] != -1) continue;
            if (color[i] == 0) {
                if (firstOdd <= n) {
                    ans[i] = firstOdd;
                    firstOdd += 3;
                } else
                if (firstZero <= n) {
                    ans[i] = firstZero;
                    firstZero += 3;
                }
            } else {
                if (firstEven <= n) {
                    ans[i] = firstEven;
                    firstEven += 3;
                } else
                if (firstZero <= n) {
                    ans[i] = firstZero;
                    firstZero += 3;
                }
            }
        }
    }
    
    for (int i = 1; i <= n; i++) {
        printf("%d ", ans[i]);
    }
    printf("\n");
    return 0;
}


Measured memory_bytes: 15476