T434253 「YAC Round 7」不动的大图书馆想要出门


帕秋莉是一个能够呆在红魔馆大图书馆一整天的宅女，而且她宅女的程度是整个幻想乡都出了名的（能和她匹敌的大概也只有居住在某不知名竹林里的蓬莱山辉夜小姐吧）。由于缺乏运动，再加上哮喘病，帕秋莉连出门都困难。 因此，帕秋莉决定对幻想乡的道路施加魔法。 幻想乡是一个 $n$ 个点 $m$ 条有向边的有向图。每个节点表示一个地区，而帕秋莉所在的红魔馆为 $1$ 号点。保证 $1$ 号点可以经过若干条道路到达任意其他地区。 第 $i$ 条有向道路可以用 $(u_i, v_i)$ 表示，说明从 $u_i$ 到 $v_i$ 有一条道路。 帕秋莉想要从红魔馆，也就是 $1$ 号点，到达任意其他地区。 为了方便她出行，她想要使得 **从 $1$ 号点到任意其他点的最短路都唯一**。 所以，帕秋莉决定对幻想乡的道路施加魔法，来改变道路的长度，具体地： - 在帕秋莉施加完魔法后，所有有向道路的长度都在 $[1, k]$ 范围内。 其中 $k$ 是帕秋莉地魔法等级。 请你帮助帕秋莉找到一种构造道路的方法，使得从 $1$ 到其他任意点的最短路都唯一。

对于每组测试数据： 第一行包含三个整数 $n, m, k$ $\;$ ($1 \le n \le 3 \times 10^5, 0 \le m \le 3 \times 10^5, 1 \le k \le 10^9$)，表示地区数量、道路个数以及魔法等级。 接下来 $m$ 行为有向道路 $(u_i, v_i)$ $\;$ ($1 \le u_i, v_i \le n$) 。 保证 $1\le \sum n, \sum m \le 3 \times 10^5$ 。 **不保证无自环和重边。**

对于每组数据： 如果有解，第一行输出 `Yes`，第二行 $m$ 个数依次输出每条边的权值；如果没有解，一行输出 `No`。 如果有多种可能的答案，你可以输出任意一种。

对于第一组数据，$1$ 号点到达每个点的路径都是唯一，自然无论怎么设置边权，最短路都是唯一的。 对于第二组数据，因为 $k=1$，所以两条边的边权都只能设置为 $1$。$1$ 号点到 $2$ 号点的最短路长度为 $1$，走两条边都可以，所以不是唯一的。