#include<bits/stdc++.h>
#include<tr1/unordered_map>
#define ri register int
using namespace std;
#define fi first
#define se second
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> poly;
#define pb push_back
const int rlen=1<<18|1,inf=0x3f3f3f3f;
const ll Inf=1e18;
char buf[rlen],*ib=buf,*ob=buf;
#define gc() (((ib==ob)&&(ob=(ib=buf)+fread(buf,1,rlen,stdin)),ib==ob)?-1:*ib++)
inline int read() {
  int ans=0;
  bool f=1;
  char ch=gc();
  while(!isdigit(ch)) f^=ch=='-',ch=gc();
  while(isdigit(ch)) ans=((ans<<2)+ans<<1)+(ch^48),ch=gc();
  return f?ans:-ans;
}
inline ll readl() {
  ll ans=0;
  bool f=1;
  char ch=gc();
  while(!isdigit(ch)) f^=ch=='-',ch=gc();
  while(isdigit(ch)) ans=((ans<<2)+ans<<1)+(ch^48),ch=gc();
  return f?ans:-ans;
}
inline int Read(char*s) {
  int tp=0;
  char ch=gc();
  while(!isdigit(ch)&&!isalpha(ch)) ch=gc();
  while(isdigit(ch)||isalpha(ch)) s[++tp]=ch,ch=gc();
  return tp;
}
namespace modular {
  const int mod=1e9+7;
  inline int add(int a,int b) { return a+b<mod?a+b:a+b-mod; }
  inline int dec(int a,int b) { return a<b?a-b+mod:a-b; }
  inline int mul(int a,int b) { return (ll)a*b%mod; }
  inline void Add(int&a,int b) { a=a+b<mod?a+b:a+b-mod; }
  inline void Dec(int&a,int b) { a=a<b?a-b+mod:a-b; }
  inline void Mul(int&a,int b) { a=(ll)a*b%mod; }
  inline int ksm(int a,int p) { int ret=1;for(;p;p>>=1,Mul(a,a)) (p&1)&&(Mul(ret,a),1);return ret; }
  inline int Inv(int a) { return ksm(a,mod-2); }
  inline int sqr(int a) { return mul(a,a); }
  inline int cub(int a) { return (ll)a*a%mod*a%mod; }
}
using namespace modular;
template<typename T> inline void ckmax(T&a,T b) { a<b?a=b:0; }
template<typename T> inline void ckmin(T&a,T b) { a>b?a=b:0; }
template<typename T> inline T gcd(T a,T b) { T t;while(b)t=a,a=b,b=t-t/a*a;return a; }
template<typename T> inline T Abs(T x) { return x<0?-x:x; }
inline int rd() { return rand()|(rand()<<15); }
const int N=1e6+5;
int n,cnt[N][3];
vector<int>e[N];
vector<int>a,b,c;
int ans[N];
bool get1(int x) {
  if(!a.size()&&!c.size()) return 0;
  if(a.size()) ans[x]=a.back(),a.pop_back();
  else ans[x]=c.back(),c.pop_back();
  return 1;
}
bool get2(int x) {
  if(!b.size()&&!c.size()) return 0;
  if(b.size()) ans[x]=b.back(),b.pop_back();
  else ans[x]=c.back(),c.pop_back();
  return 1;
}
bool dfs(int p,int ft,int col) {
  bool f;
  if(col==1) f=get1(p);
  else f=get2(p);
  if(!f) return 0;
  for(ri i=0,v;i<(int)e[p].size();++i) if((v=e[p][i])!=ft) f&=dfs(v,p,3-col);
  return f;
}
int mxdep=0,cnt1=0,cnt2=0,de[N];
void Dfs(int p,int ft,int col,int dep=0) {
  bool f;
  ckmax(mxdep,dep);
  de[p]=dep;
  if(col==1) ++cnt1;
  else ++cnt2;
  for(ri i=0,v;i<(int)e[p].size();++i) if((v=e[p][i])!=ft) Dfs(v,p,3-col,dep+1);
}
inline bool Test(int col) {
  a.clear(),b.clear(),c.clear();
  for(ri i=1;i<=n;i+=3) a.pb(i);
  for(ri i=2;i<=n;i+=3) b.pb(i);
  for(ri i=3;i<=n;i+=3) c.pb(i);
  return dfs(1,0,col);
}
inline void print() { for(ri i=1;i<=n;++i) cout<<ans[i]<<' '; }
inline void check() {
  int rt=1;
  for(ri i=2;i<=n;++i) if(e[i].size()==1) rt=i;
  Dfs(rt,0,1);
  if(mxdep<3) {
    for(ri i=1;i<=n;++i) cout<<i<<' ';
    exit(0);
  }
  else {
    for(ri i=1;i<=n;i+=3) a.pb(i);
    for(ri i=2;i<=n;i+=3) b.pb(i);
    for(ri i=3;i<=n;i+=3) c.pb(i);
    bool ff=cnt1>cnt2;
    if(cnt1>cnt2) swap(cnt1,cnt2);
    if(cnt1<=n/3) {
      for(ri i=1;i<=n;++i) if(!((de[i]&1)^ff)) {
        ans[i]=c.back(),c.pop_back();
      }
      for(ri i=1;i<=n;++i) if(!ans[i]) {
        if(b.size()) ans[i]=b.back(),b.pop_back();
        else if(c.size()) ans[i]=c.back(),c.pop_back();
        else ans[i]=a.back(),a.pop_back();
      }
    }
    else {
      for(ri i=1;i<=n;++i) if(!((de[i]&1)^ff)) {
        if(a.size()) ans[i]=a.back(),a.pop_back();
        else ans[i]=c.back(),c.pop_back();
      }
      else {
        if(b.size()) ans[i]=b.back(),b.pop_back();
        else ans[i]=c.back(),c.pop_back();
      }
    }
    for(ri i=1;i<=n;++i) cout<<ans[i]<<' ';
    exit(0);
  }
}
int main() {
  #ifdef ldxcaicai
  freopen("lx.in","r",stdin);
  #endif
  n=read();
  for(ri i=1,u,v;i<n;++i) {
    u=read(),v=read();
    e[u].pb(v),e[v].pb(u);
  }
  check();
  return 0;
}

Measured memory_bytes: 52220