oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

redblue Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

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

redblue.html

Problem Description

There are a total of N towns, connected by a total of R roads. Each road i connects cities Ai and Bi, and is either coloured red or blue. If the road is coloured red, Ci = 0, and otherwise Ci = 1. It is guaranteed that it is possible to travel between any two towns using only these roads.

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, Ai, Bi and Ci.

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 ≤ Ai, Bi < N, 0 ≤ Ci ≤ 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

Graph Theory

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
129211s256MBMinimum
230421s256MBMinimum
341621s256MBMinimum
4021s256MBMinimum

Judge Compile Command

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

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.