神仙题，奇奇怪怪的性质分析，基本没有套路。
思路
分类讨论。
1. \(k=2\)
只用一次 dfs 交替染色即可。可以直接在程序中特判。
2. 只有一条链
可以按照 \(1,2,3, \cdots , k,1,2,\cdots\) 这样染色。
3. 其它
这种情况中有无解的可能。
如果有三个及以上的点与它相连，令相连着的三条链的长度分别为 \(a,b,c\) 。
不妨设 \(a \ge b \ge c\) 。
若 \(b+c \ge k\) ，则无解。
简单的证明：显然得证。
容易得到 \(a+b \ge a+c \ge b+c \ge k\) 。
我们可以先染 \(a\) 链上的色。
由题目要求，可以得到 \(b\) 链和 \(c\) 链上有一段的颜色是一样的。
又因为 \(b+c \ge k\) 则 \(b\) 链和 \(c\) 链可以组成一个长度为 \(k\) 的链。
因为有一段的颜色相等，所以与题意不符。所以无解。
这也可以解释为什么要特判 \(k=2\) 的情况。因为它不可能出现在两个不同的链上。
实现
怎么找这个点呢？点分治
为了尽快找到这个不满足条件的点，我们先找到直径的一个端点。
假设可以满足题目条件，我们就按深度染色，在染色的同时求 \(b\) 和 \(c\) （最长链和次长链）。
众所周知，树的直径有个性质：端点离树上所有的点的距离最大。
如果在此基础上最大化了这个 \(b\) 和 \(c\) ，还是没有找到无解的情况，那么它就一定有解了。
然后再从这个节点开始染色，同一层的点染上同一个颜色。
代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
#define rep(i,a,b) for(register int i=a;i<=b;++i)
#define Rep(i,a,b) for(register int i=a;i>=b;--i)
inline int read()
{
int x=0;bool f=0;char ch;
do{ch=getchar();f|=(ch=='-');}while(!isdigit(ch));
do{x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}while(isdigit(ch));
return f?-x:x;
}
inline void write(int x)
{
if(x<0)x=-x,putchar('-');
if(x>9)write(x/10);putchar(x%10+'0');
}
inline void writesp(int x)
{
write(x);putchar(' ');
}
inline void writeln(int x)
{
write(x);puts("");
}//IO
int head[maxn],to[maxn<<1],nxt[maxn<<1],tot=0;
void add(int u,int v)
{
nxt[++tot]=head[u];
head[u]=tot;
to[tot]=v;
}
int dep[maxn];
void dfs(int u,int fa)
{
dep[u]=dep[fa]+1;
for(register int i=head[u];i;i=nxt[i])
{
int v=to[i];
if(v==fa)continue;
dfs(v,u);
}
}//求深度
bool tag[maxn];//给直径上的点打的标记
void diam(int u,int fa)
{
for(register int i=head[u];i;i=nxt[i])
{
int v=to[i];
if(v==fa)continue;
diam(v,u);
if(tag[v])tag[u]=true;//如果这个点的子节点是直径上面的，那么它也是直径上的
}
}
int n,k;
int len,f[maxn],g[maxn],col[maxn];//f,g为最长链和次长链
void color2(int u,int fa,int op)//这个函数是针对直径外的点的
{//跟 color1 差不多
if(op)col[u]=col[fa]%k+1;
else col[u]=col[fa]-1+(col[fa]==1)*k;
for(register int i=head[u];i;i=nxt[i])
{
int v=to[i];
if(v==fa)continue;
color2(v,u,op);
if(f[v]>=f[u])g[u]=f[u],f[u]=f[v]+1;
else if(f[v]>=g[u])g[u]=f[v]+1;
if(g[v]>=g[u])g[u]=g[v]+1;
}
if(f[u]+g[u]+1>=k)
{
puts("No");exit(0);
}
}
void color1(int u,int fa)//这个函数是针对直径上的点的
{
col[u]=col[fa]%k+1;
for(register int i=head[u];i;i=nxt[i])
{
int v=to[i];
if(v==fa)continue;
if(tag[v]){color1(v,u);continue;}//如果在直径上就直接染色
if(dep[u]*2-1<=len)//如果 u 在直径的前半段
color2(v,u,0);
else color2(v,u,1);//否则
//Ps:
//这里的染色其实是以直径的中点为根来染色的，可是dfs是由直径的端点开始的
if(f[v]>=f[u])g[u]=f[u],f[u]=f[v]+1;
else if(f[v]>=g[u])g[u]=f[v]+1;
if(g[v]>=g[u])g[u]=g[v]+1;
//维护最长链和次长链
}
if(f[u]+g[u]+1>=k)
{
puts("No");exit(0);
}
if(f[u]&&f[u]+dep[u]>=k&&f[u]+len-dep[u]+1>=k)
{
puts("No");exit(0);
}
}
//注意：
//对于非直径上的点，次长链和最长链一定出现在它的子树中
//对于在直径上的点，次长链和最长链还有可能出现在直径上，所以要增加一个判断
int main()
{
n=read(),k=read();
rep(i,1,n-1)
{
int u=read(),v=read();
add(u,v);
add(v,u);
}//输入
dfs(1,0);
if(k==2)
{
puts("Yes");
rep(i,1,n)
{
writesp((dep[i]&1)?1:2);//交替染色
}
return 0;
}//特判 k=2 的情况
int temp=0;
rep(i,1,n)
{
if(dep[i]>dep[temp])temp=i;
}
memset(dep,0,sizeof dep);
dfs(temp,0);
int s=0;
rep(i,1,n)
{
if(dep[i]>dep[s])s=i;
}//s是直径的端点
tag[s]=1;diam(temp,0);//给直径打标记
col[0]=k;
len=dep[s];//求直径的长度（这个在函数中有用）
color1(temp,0);//染色，同时判断是否无解 （如果无解就直接退出程序）
puts("Yes");
rep(i,1,n)writesp(col[i]);
return 0;
}