#### Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

## Problem Description

There are a total of *N* towns, connected by a total of *R* roads. Each road *i* connects cities *A _{i}* and

*B*, and is either coloured red or blue. If the road is coloured red,

_{i}*C*= 0, and otherwise

_{i}*C*= 1. It is guaranteed that it is possible to travel between any two towns using only these roads.

_{i}
The mayor, wanting to save money, has decided to close some of these roads, keeping only *N* - 1 roads. It must still be possible to travel between any two towns using open roads, and to preserve the scenic beauty of the city, there must be an equal number of red roads and blue roads remaining. Help the mayor decide if this is possible, and if so, construct a possible set of roads to keep such that the above conditions are fulfilled.

## Input

The first line of input will contain two integers, *N* and *R*.

The next *R* lines of input will contain three integers each, *A _{i}*,

*B*and

_{i}*C*.

_{i}## Output

The first line of output should contain a string, 'YES' or 'NO', indicating whether it is possible to construct a subset of roads to keep to fulfill the mayor's conditions.

If it is possible, the second line of output should contain a space-seperated list of integers, listing the IDs of the roads to keep. The roads are numbered from 0 to *R* - 1 in the order of input.

## Limits

For all subtasks: 0 ≤ A_{i}, B_{i} < N, 0 ≤ C_{i} ≤ 1.

Subtask 1 (29%): 2 ≤ N = R ≤ 1000.

Subtask 2 (30%): 2 ≤ N ≤ 1000, 1 ≤ R ≤ 2500.

Subtask 3 (41%): 2 ≤ N ≤ 2000, 1 ≤ R ≤ 500000.

Subtask 4 (0%): Sample Testcases.

## Sample Input 1

3 3 0 1 0 0 2 1 1 2 0

## Sample Output 1

YES 0 1

## Sample Input 2

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

## Sample Output 2

NO

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 29 | 21 | 1s | 256MB | Minimum |

2 | 30 | 42 | 1s | 256MB | Minimum |

3 | 41 | 62 | 1s | 256MB | Minimum |

4 | 0 | 2 | 1s | 256MB | Minimum |

### Judge Compile Command

g++-8 ans.cpp -o redblue -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512