P16442 [XJTUPC 2026] 机房分配

为了降低程序设计竞赛中的作弊风险，学校需要将 $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$ 个机房。 如果存在多种分配方案，输出任意一种即可。