Введение в haskell 2024

Problem A. Road repairing ≡

problems
visible spaces
basic formulae
wide text
editor

Author:	Timofey S. Chistyakov	Time limit:	5 sec
Input file:	input.txt	Memory limit:	6 Mb
Output file:	output.txt

Statement

A city road network contains N intersections connected with M roads. It is possible to reach any intersection from any other. Before winter started, city major decided to repair some roads in the city, so they wouldn't be totally ruined by spring time.

However, due to magnificent celebration of the city anniversary, city budget is considerably exhausted. That is why city administration wants to repair as little roads as possible. Some roads are already in satisfactory condition and don't need repairing. As to the other roads, the major wants to repair only those that cannot be driven around, even by the bad roads.

Your task is to help the major to obtain the list of the roads that are to be repaired.

Input file format

Input file contains numbers N M, then M triads of numbers a_i, b_i, c_i. Each triad describes one road connecting intersections a_i, b_i. c_i is 1 if the road is in satisfactory condition and 0 otherwise.

Output file format

Output file should contain the number of roads to be repaired, then the list of these roads. Each road should be described by two numbers of connected intersections. The roads should be sorted by first intersection, secondary sorted by second intersection. Within each road description the intersection with less number should come first.

Constraints

1 ≤ N, M ≤ 100000,

Sample tests

No.	Input file (`input.txt`)	Output file (`output.txt`)
1	`7 8 1 2 0 2 3 1 1 3 0 2 4 1 5 3 0 5 6 1 6 7 0 5 7 0`	`1 3 5`