Description

托伦有许多旅游景点。我们的导游准备了一份包含 $m$ 条单向步行路线的清单，这些路线连接了市中心的 $n$ 个集合点。步行路线编号为 1 到 $m$，集合点编号为 1 到 $n$。每条步行路线从一个集合点出发，到达另一个集合点，途中可以参观一个景点。不同的步行路线可能参观相同的景点，并且同一对集合点之间可能存在多条步行路线。我们希望在休息日组织一次有趣的游览。

一次游览是指一系列步行路线，其中每条步行路线的起点是前一条步行路线的终点。此外，最后一条步行路线的终点必须是最初第一条步行路线的起点。

如果一次游览中不会连续两次参观相同的景点，则称其为有趣的游览。换句话说，游览中任意两条连续的步行路线参观的景点必须不同，并且第一条和最后一条步行路线参观的景点也必须不同。注意，我们不关心非连续的步行路线是否参观相同的景点。特别地，同一条步行路线可以在游览中多次使用（但不能连续使用两次）。

你的任务是判断是否可以组织一次有趣的游览，如果可以，则找到一条这样的游览。你可以输出任意一条包含不超过 $m$ 条步行路线的有趣游览。可以证明，如果存在有趣的游览，那么一定存在一条不超过 $m$ 条步行路线的有趣游览。

Input Format

第一行包含一个正整数 $t$（$1 \leq t \leq 5 \cdot 10^5$），表示测试用例的数量。

每个测试用例的第一行包含两个正整数 $n$ 和 $m$（$2 \leq n$，$1 \leq m$），分别表示集合点的数量和步行路线的数量。

接下来的 $m$ 行描述了 $m$ 条步行路线。第 $i$ 行包含三个正整数 $x_i$、$y_i$ 和 $c_i$（$1 \leq x_i, y_i \leq n$，$x_i \neq y_i$，$1 \leq c_i \leq m$），表示第 $i$ 条步行路线从集合点 $x_i$ 出发，到达集合点 $y_i$，并且参观的景点编号为 $c_i$。

设 $N$ 和 $M$ 分别表示所有测试用例中 $n$ 和 $m$ 的总和。你可以假设 $N, M \leq 10^6$。

Output Format

对于每个测试用例，第一行输出 YES 表示可以组织有趣的游览，否则输出 NO。如果可以组织，则在第二行首先输出一个正整数 $k$（$2 \leq k \leq m$），表示构成有趣游览的步行路线数量。随后输出 $k$ 个用单个空格分隔的整数 $p_1, p_2, \ldots, p_k$，这些数字描述了一条有趣的游览，其中我们首先走步行路线 $p_1$，然后是 $p_2$，依此类推，最后走步行路线 $p_k$ 回到最初的集合点。

5
3 3
1 2 1
2 3 2
3 1 1
3 3
2 1 1
1 3 3
3 1 2
2 2
1 2 2
1 2 1
5 6
1 2 1
2 3 2
3 1 1
1 4 3
4 5 4
5 1 3
4 4
1 3 4
3 2 1
2 3 2
2 3 2

NO
YES
2 2 3
NO
YES
6 3 4 5 6 1 2
YES
4 2 4 2 3

Hint

示例中第 4 个测试用例的图示。箭头表示集合点之间的步行路线。

评分

翻译由 DeepSeek V3 完成