Задачи по теме "Теория игр"

Problem B. Uncertain Finish ≡

problems
visible spaces
basic formulae
wide text
editor

Author:	T.Chistyakov, A. Klenin	Time limit:	2 sec
Input file:	input.txt	Memory limit:	32 Mb
Output file:	output.txt

Statement

At the running contest, jury used a new computerized stopwatch system to ensure the most accurate measuring of results. Unfortunately, despite very successfull trials, the system malfunctioned during the actual contest.

Jury was so confident in the new system that it did not use the old mechanical stopwatches. So the only way to determine outcome was to compare visual impressions of the people watching the contest. M such impressions were recorded, each in one of two forms: "runner A finished before runner B" and "runners A and B finished at the same time".

You task is to assign a place p_i to each of N runners, such that

If there is a record that A and B finished at the same time, then p_A = p_B.
If there is a record that A finished before B, then p_A < p_B.

Additionally, places must be allocated as densely as possible, i.e. 1 ≤ p_i ≤ K for minimum possible value of K.

Input file format

Input file contains integers N M followed by M pairs A_i B_i c_i, where c_i = 0 means the record "runners A_i and B_i finished at the same time", c_i = 1 means the record "runner A_i finished before B_i".

Output file format

Output file must contain either a single number −1, if the places could not be assigned, or a sequence of N numbers p_i. If several solutions exist, output any of them.

Constraints

1 ≤ N ≤ 10000, 0 ≤ M ≤ 10⁶, 1 ≤ A_i, B_i ≤ N

Sample tests

No.	Input file (`input.txt`)	Output file (`output.txt`)
1	`3 2 3 2 1 2 1 0`	`2 2 1`