#include <bits/stdc++.h>
using namespace std;

#define F(i,a,b) for(long long  i =a; i<b; i++)
#define rF(i,a,b) for(long long i=a-1; i>=b;i--)
#define endl "\n"
#define min1(x,y,z) min(x, min(y,z))
#define max1(x,y,z) max(x, max(y,z))
#define input_vector(v,n,type) vector<type> v;for(int i=0;i<n;i++){type x;cin>>x;v.push_back(x);}
#define IOS ios_base::sync_with_stdio(false);  cin.tie(NULL);  cout.tie(NULL);
#define int long long
#define inf (1LL<<61)
typedef pair<int,int> ii;
typedef vector<pair<int,int>> vii;
typedef vector<int> vi;



int32_t main()
{
      IOS;

      int n;
      cin>>n;
      vector<int> adj[n];
      for (int i = 0; i < n-1; i++) {
            int x, y;
            cin>>x>>y;
            x--; y--;
            adj[x].push_back(y);
            adj[y].push_back(x);
      }

      queue<int> q;
      vector<int> color(n, -1);
      q.push(0);
      color[0] = 0;
      vector<int> cnt(2, 0);
      cnt[0]++;

      while (!q.empty()) {
            int cur = q.front();
            q.pop();
            for (auto u: adj[cur]) {
                  if (color[u] == -1) {
                        color[u] = 1-color[cur];
                        cnt[color[u]]++;
                        q.push(u);
                  }
            }
      }
      //cout<<cnt[0]<<" "<<cnt[1]<<endl;

      
      int lesser = min(cnt[0], cnt[1]);
      int mincolor = (cnt[0] < cnt[1] ? 0 : 1);
      
      vector<int> ans(n, -1);
      int k, j, k1, k2;
      if (lesser <= n/3) {
            k = 1;
            for (int i = 0; i < n; i++) {
                  if (color[i] == mincolor) {
                        ans[i] = 3*k;
                        k++;
                  }
            }
            j = 1;
            for (int i = 0; i < n; i++) {
                  if (ans[i] == -1) {
                        if (j%3) {
                              if (j > n) {
                                    ans[i] = 3*k;
                                    k++;
                              } else {
                                    ans[i] = j++;
                              }
                        }
                        else {
                              if (j+1 > n) {
                                    ans[i] = 3*k;
                                    k++;
                              } else {
                                    ans[i] = ++j;
                                    j++;
                              }
                        }
                  }
            }
      }  else {
            k1 = 0, k2 = 0, j = 1;
            for (int i = 0; i < n; i++) {
                  if (color[i] == mincolor) {
                        ans[i] = 3*k1+1;
                        k1++;
                  } else {
                        ans[i] = 3*k2+2;
                        k2++;
                  }
            }
            int j = 1;
            for (int i = 0; i < n; i++) {
                  if (ans[i] == -1 || ans[i] > n) {
                        ans[i] = 3*j;
                        j++;
                  }
            }
      }

      for (int i = 0; i < n; i++) {
            cout<<ans[i]<<" ";
      }
      cout<<endl;

      
            
            



            



      


        
























            return 0;
}

Measured memory_bytes: 18280