#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
const int ans[9][9]={{},
{1,1},
{1,1,1},
{2,1,1,2},
{2,1,1,2,2},
{3,1,1,2,2,3},
{3,1,1,2,2,3,3},
{4,1,1,2,2,3,3,4}};
int n;
int main(){
	freopen("color.in","r",stdin);
	freopen("color.out","w",stdout);
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n;
	if(n<=7){
		cout<<ans[n][0]<<'\n';
		for(int i=1;i<=n;i++){
			cout<<ans[n][i]<<' ';
		}
	}
	else{
		cout<<4<<'\n';
		for(int i=1;i<=n;i++){
			cout<<(i+3)%4+1<<' ';
		}
	}
	return 0;
}
}
int main(){return asbt::main();}

#include<bits/stdc++.h>
#define ll long long
#define il inline
#define pb push_back
using namespace std;
namespace asbt{
const int maxn=3e5+5;
int n,m,dep[maxn],fa[maxn];
vector<int> e[maxn];
namespace LCA{
	int cnt,dfn[maxn],oula[maxn<<1],idx[maxn<<1];
	il void dfs(int u,int fth){
		dfn[u]=++cnt,oula[cnt]=cnt;
		idx[cnt]=u,fa[u]=fth;
		dep[u]=dep[fth]+1;
		for(int v:e[u]){
			if(v==fth){
				continue;
			}
			dfs(v,u);
			oula[++cnt]=dfn[u];
		}
	}
	struct{
		int Log[maxn<<1],st[maxn<<1][22];
		il void init(){
			for(int i=2;i<=cnt;i++){
				Log[i]=Log[i>>1]+1;
			}
			for(int i=1;i<=cnt;i++){
				st[i][0]=oula[i];
			}
			for(int j=1;j<=Log[cnt];j++){
				for(int i=1;i+(1<<j)-1<=cnt;i++){
					st[i][j]=min(st[i][j-1],st[i+(1<<(j-1))][j-1]);
				}
			}
		}
		il int query(int l,int r){
			int p=Log[r-l+1];
			return min(st[l][p],st[r-(1<<p)+1][p]);
		}
	}ST;
	il void init(){
		dfs(1,0),ST.init();
	}
	il int lca(int u,int v){
		if(dfn[u]>dfn[v]){
			swap(u,v);
		}
		return idx[ST.query(dfn[u],dfn[v])];
	}
	il int dis(int u,int v){
		return dep[u]+dep[v]-dep[lca(u,v)]*2;
	}
}
using LCA::lca;
using LCA::dis;
struct{
	int tot,rt[maxn],ls[maxn*24],rs[maxn*24],sum[maxn*24];
	il void pushup(int id){
		sum[id]=sum[ls[id]]+sum[rs[id]];
	}
	il void insert(int &p,int q,int l,int r,int x){
		if(!p){
			p=++tot;
		}
		if(l==r){
			sum[p]=sum[q]+1;
			return ;
		}
		int mid=(l+r)>>1;
		if(x<=mid){
			rs[p]=rs[q];
			insert(ls[p],ls[q],l,mid,x);
		}else{
			ls[p]=ls[q];
			insert(rs[p],rs[q],mid+1,r,x);
		}
		pushup(p);
	}
	il int query(int id,int l,int r,int x){
		if(!id){
			return 0;
		}
		if(l==r){
			return sum[id];
		}
		int mid=(l+r)>>1;
		return x<=mid?query(ls[id],l,mid,x):query(rs[id],mid+1,r,x);
	}
	il void insert(int u,int x){
		insert(rt[u],rt[fa[u]],-6e5,6e5,x);
	}
	il int query(int u,int x){
		return query(rt[u],-6e5,6e5,x);
	}
}S1,S2;
il void dfs(int u,int fa){
	S1.insert(u,u+dep[u]);
	S2.insert(u,u-dep[u]);
	for(int v:e[u]){
		if(v==fa){
			continue;
		}
		dfs(v,u);
	}
}
int main(){
	freopen("query.in","r",stdin);
	freopen("query.out","w",stdout);
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n>>m;
	for(int i=1,u,v;i<n;i++){
		cin>>u>>v;
		e[u].pb(v),e[v].pb(u);
	}
	LCA::init(),dfs(1,0);
	while(m--){
		int u,v;
		cin>>u>>v;
		int w=lca(u,v),k=dis(u,v)-dep[v];
		cout<<S1.query(u,dep[u])-S1.query(fa[w],dep[u])+S2.query(v,k)-S2.query(w,k)<<'\n';
	}
	return 0;
}
}
int main(){return asbt::main();}