You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

作为 luogu 网红的帆巨，有非常多狂热的粉丝，而我们的帆巨也很喜欢面基，寻找遍布大江南北的粉丝们。

题目描述

帆巨所在的家乡的地图是一张有 $n$ 个节点 $m$ 条有向道路的有向图，每个节点都是一个城市，而帆巨所在的城市是 $1$ 号城市，并且 $1$ 号城市总是可以通过若干道路到达其他任何城市。

第 $i$ 条道路从 $x_i$ 号城市出发到达 $y_i$ 号城市，长度为 $z_i$。

帆帆现在要从他的 $1$ 号城市前往各个城市面基。

精通 spfa 算法的帆帆在面基的过程中自然会按照长度和最短的路径去其他城市。

但是帆帆有选择困难症，他希望从 $1$ 号城市到达每一座城市的最短路径都是唯一的，所以他决定施加魔法，改变所有道路的长度，具体地：

帆巨施加魔法后，对于每一条道路的长度，都可以 独立地 将其变成一个 $[1,k]$ 范围内的整数，其中 $k$ 是帆巨的魔法等级。

但帆巨所在的世界的地图和他的魔法等级一直在变，总共会变 $T$ 次，所以他希望你对 $T$ 次询问都给出一种构造方法使得帆巨不会纠结或者报告无解。

输入格式

第一行一个整数 $T$ 表示数据组数。

接下来 $T$ 组，每组先是三个整数 $n,m,k$，接着 $m$ 行描述有向道路 $(x_i,y_i)$。

不保证无自环无重边。

输出格式

对于每组数据，如果有解，第一行输出 Yes，第二行 $m$ 个数依次输出每条边的权值；如果没有解，一行输出 No。

本题采用 special judge 评测，也就是说，如果有多种可能的答案，你可以输出任意一种。

2
3 2 3
1 2
2 3
2 2 1
1 2
1 2

Yes
1 2
No

提示

【样例解释】

对于第一组数据，$1$ 号点到达每个点的路径都是唯一，自然无论怎么设置边权，最短路都是唯一的。

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

【数据范围】

本题采用捆绑测试。

对于 $20\%$ 的数据，$n,m\leq 5$。

对于另外 $20\%$ 的数据，$k=1$。

对于另外 $20\%$ 的数据，$m=n-1$。

对于另外 $20\%$ 的数据，$k=10^9$。

对于 $100\%$ 的数据，$n\ge 1$，$m\ge 0$，$1\le \sum n,\sum m\leq 3\times 10^5$，$1\leq k \leq 10^9$，$1\le x_i,y_i\le n$。