题目描述

为了降低程序设计竞赛中的作弊风险，学校需要将 $n$ 名参赛同学分配到 $k$ 个机房中参加比赛。

已知部分同学之间彼此较为熟悉。我们用一张带权无向图 $G=(V,E)$ 来描述这些关系：

• 每个点表示一名同学；
• 每条边表示两名同学之间存在一定关系；
• 边权为正整数，表示这两名同学的关系程度，权值越大，说明两人越熟悉；
• 图 $G$ 为无自环、无重边的简单图。

若同一机房内同学之间的总关系程度过高，则会增加监考压力。

对于某个机房，所有两端点均被分配到该机房的边的权值和，称为该机房的风险值。

设整张图所有边权之和为 $S = \sum\limits_{e \in E} w_e$， 其中 $w_e$ 表示边 $e$ 的权值。

学校规定，所有机房的风险值之和不能超过 $\left\lceil \frac{S}{k} \right\rceil$。

现在需要你判断，是否存在一种分配方案，使得：

• 每名同学恰好被分配到一个机房；
• 所有机房的风险值之和不超过 $\left\lceil \frac{S}{k} \right\rceil$。

若存在，请输出一种满足要求的分配方案。如果存在多种分配方案，输出任意一种即可。

请注意：允许某一个机房内没有分配任何同学；不保证图 $G$ 连通。

输入格式

输入的第一行，包含三个整数 $n,m$ 和 $k$（$1 \le k \le n \le 5\times 10^5, 0 \le m \le 5\times 10^5$），用一个空格分隔，分别表示同学人数、关系条数以及机房数量。

接下来 $m$ 行，每行包含三个整数 $u,v$ 和 $w$（$1 \le u,v \le n, u \ne v, 1 \le w \le 10^9$），用一个空格分隔，表示第 $u$ 名同学与第 $v$ 名同学之间存在一条权值为 $w$ 的无向边。

保证输入图中不存在重边。

输出格式

如果不存在满足要求的分配方案，输出一行，仅包含一个字符串 $\tt{No}$。

否则输出两行，其中：

• 第一行包含一个字符串 $\tt{Yes}$；
• 第二行包含 $n$ 个整数 $a_1,a_2,\cdots,a_n$（$1 \le a_i \le k$），用一个空格分隔，其中 $a_i$ 表示第 $i$ 名同学被分配到第 $a_i$ 个机房。

如果存在多种分配方案，输出任意一种即可。

4 4 2
1 2 1
2 3 1
3 4 1
4 1 1

Yes
1 2 1 2