#pragma GCC optimize("O3")
        #pragma comment(linker, "/stack:200000000")
        #pragma GCC optimize("unroll-loops")
         
        #include <algorithm>
        #include <bitset>
        #include <cassert>
        #include <chrono>
        #include <cmath>
        #include <complex>
        #include <cstdio>
        #include <cstdlib>
        #include <cstring>
        #include <ctime>
        #include <deque>
        #include <functional>
        #include <iomanip>
        #include <iostream>
        #include <iterator>
        #include <limits>
        #include <climits>
        #include <list>
        #include <map>
        #include <numeric>
        #include <queue>
        #include <random>
        #include <ratio>
        #include <set>
        #include <sstream>
        #include <stack>
        #include <string>
        #include <unordered_map>
        #include <unordered_set>
        #include <utility>
        #include <vector>
        using namespace std;
         
        typedef long long ll;
        typedef long double LD;
        #define int ll
        #define double LD
        #define pb push_back
        #define mp make_pair
        #define REP(i,n) for (int i = 0; i < n; i++)
        #define loop(i,n) for (int i = 0; i < n; i++)
        #define FOR(i,a,b) for (int i = a; i < b; i++)
        #define REPD(i,n) for (int i = n-1; i >= 0; i--)
        #define FORD(i,a,b) for (int i = a; i >= b; i--)
        #define remax(a,b) a = max(a,b)
        #define remin(a,b) a = min(a,b)
        #define mem(a, b) memset(a, b, sizeof a)
        #define append push_back
        #define all(v) v.begin(),v.end()
        #define F first
        #define S second
        #define print(x) cout << (x) << endl
        #define PRECISION(x) cout << fixed << setprecision(x)
        #define FAST_IO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
         
        const double PI=acos(-1);
        const int MOD = 1000000007;
        const int FMOD = 998244353;
        const double eps = 1e-9;
         
        mt19937 RNG(chrono::steady_clock::now().time_since_epoch().count()); 
      	
      	vector<int> v[300000];
      	int dist[300000];
      	vector<int> num[3];
      	int ans[300000];
     	void dfs(int src,int par)
     	{
     		for(auto x:v[src])
     		{
     			if(x!=par)
     			{
     				dist[x]=dist[src]+1;
     				dfs(x,src);
				 }
			 }
		 }
    	signed main()
    	{
    		int n;
    		cin>>n;
    		for(int i=0;i<n-1;i++)
    		{
    			int a,b;
    			cin>>a>>b;
    			a--;
    			b--;
    			v[a].push_back(b);
    			v[b].push_back(a);
			}
			dist[0]=0;
			dfs(0,-1);
			for(int i=1;i<=n;i++)
			{
				num[i%3].push_back(i);
			}
			int odd=0,even=0;
			for(int i=0;i<n;i++)
			{
				if(dist[i]%2)
				odd++;
				else
				even++;
			}
			if(odd<=num[0].size())
			{
				for(int i=0;i<n;i++)
				{
					if(dist[i]%2)
					{
						ans[i]=num[0].back();
						num[0].pop_back();
					}
					else
					{
						if(num[1].size())
						{
							ans[i]=num[1].back();
							num[1].pop_back();
						}
						else if(num[2].size())
						{
							ans[i]=num[2].back();
							num[2].pop_back();
						}
						else if(num[0].size())
						{
							ans[i]=num[0].back();
							num[0].pop_back();
						}
					}
				}
			}
			else if(even<=num[0].size())
			{
				for(int i=0;i<n;i++)
				{
					if(dist[i]%2==0)
					{
						ans[i]=num[0].back();
						num[0].pop_back();
					}
					else
					{
						if(num[1].size())
						{
							ans[i]=num[1].back();
							num[1].pop_back();
						}
						else if(num[2].size())
						{
							ans[i]=num[2].back();
							num[2].pop_back();
						}
						else if(num[0].size())
						{
							ans[i]=num[0].back();
							num[0].pop_back();
						}
					}
				}
			}
			
			else
			{
				for(int i=0;i<n;i++)
				{
					if(dist[i]%2)
					{
						if(num[1].size())
						{
							ans[i]=num[1].back();
							num[1].pop_back();
						}
						else if(num[0].size())
						{
							ans[i]=num[0].back();
							num[0].pop_back();
						}
					}
					else
					{
						if(num[2].size())
						{
							ans[i]=num[2].back();
							num[2].pop_back();
						}
						else if(num[0].size())
						{
							ans[i]=num[0].back();
							num[0].pop_back();
						}
					}
				}
			}
			for(int i=0;i<n;i++)
			cout<<ans[i]<<" ";
		}

Measured memory_bytes: 23912