#P12427. [BalticOI 2025] Tour

    ID: 14026 远端评测题 4000ms 1024MiB 尝试: 0 已通过: 0 难度: 5 上传者: 标签>2025Special Judge图遍历BalticOI(波罗的海)

[BalticOI 2025] Tour

题目描述

There are many tourist attractions in Toruń. Our tour guides prepared a list of mm one-way walks connecting nn meeting points in the city center. The walks are numbered from 1 to mm and similarly the meeting points are numbered from 1 to nn. Each walk leads from one meeting point to another and allows the participants to see a single attraction on the way. It might be possible to see the same attraction on different walks and there might be multiple walks between the same pair of meeting points. We would like to organise an interesting tour on our day off.

A tour is a sequence of walks, such that every walk starts at the meeting point where the previous one ends. Furthermore, the last walk ends at the meeting point where the very first walk begins.

We call such a tour interesting if it doesn't contain the same attraction twice in a row. In other words, every two consecutive walks from the tour allow us to see different attractions, and additionally the very first and very last walks from the tour allow us to see different attractions as well. Note that we do not mind if some non-consecutive walks allow us to see the same attraction. In particular, the same walk might be used multiple times on the tour (but not twice in a row).

Your task is to check if it is possible to form an interesting tour, and if so to find one. You can output any interesting tour that consists of at most mm walks. It can be proven that if there exists an interesting tour, then there exists one consisting of at most mm walks.

输入格式

The first line contains a positive integer tt (1t51051 \leq t \leq 5 \cdot 10^5) denoting the number of test cases.

The first line of each test case contains positive integers nn and mm (2n2 \leq n, 1m1 \leq m) denoting the number of meeting points and walks, respectively.

Each of the subsequent mm lines describes one of the mm walks. The ii-th line contains three positive integers xi,yix_i, y_i and cic_i (1xi,yin1 \leq x_i, y_i \leq n, xiyix_i \neq y_i, 1cim1 \leq c_i \leq m), which indicate that the ii-th walk starts at the meeting point xix_i, ends at the meeting point yiy_i, and allows us to see the attraction cic_i.

Let NN and MM denote the sum of nn and mm, respectively, over all test cases. You can assume that N,M106N, M \leq 10^6.

输出格式

For each test case, in the first line you should output YES if it is possible to organise an interesting tour and NO otherwise. In the former case, the second line should first contain a positive integer kk (2km2 \leq k \leq m) denoting the number of walks forming the interesting tour. This should be followed by kk integers p1,p2,,pkp_1, p_2, \ldots, p_k separated by single spaces. These numbers should describe an interesting tour, where we first follow walk p1p_1, then p2p_2, and so on, and finally we follow walk pkp_k returning to the original meeting point.

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

提示

Illustration of the 4th test case from the example. The arrows represent the walks between meeting points.

Scoring

Subtask Constraints Points
1 m10m \leq 10 and t100t \leq 100 9
2 M5000M \leq 5000 23
3 M5104M \leq 5 \cdot 10^4 19
4 M2105M \leq 2 \cdot 10^5 25
5 No additional constraints. 24