Problem B. Uncertain Finish ≡

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 pi to each of N runners, such that

  1. If there is a record that A and B finished at the same time, then pA = pB.
  2. If there is a record that A finished before B, then pA < pB.

Additionally, places must be allocated as densely as possible, i.e. 1 &le; pi &le; K for minimum possible value of K.

Input file format

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

Output file format

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

Constraints

1 &le; N &le; 10000, 0 &le; M &le; 106, 1 &le; Ai, Bi &le; N

Sample tests

No. Input file (input.txt) Output file (output.txt)
1 
3 2
3 2 1
2 1 0
 
2 2 1
0.052s 0.008s 13