eolymp
bolt
Try our new interface for solving problems
Problems

Insider's Information

Insider's Information

Time limit 1 second
Memory limit 128 MiB

Ian works for a rating agency that publishes ratings of the best universities. Irene is a journalist whoplans to write a scandalous article about the upcoming rating.

Using various social engineering techniques (let's not get into more details), Irene received some insider's information from Ian.

Specifically, Irene received several triples (a[i], b[i], c[i]), meaning that in the upcoming rating, university b[i] stands between universities a[i] and c[i]. That is, either a[i] comes before b[i] which comes before c[i], or the opposite. All triples told by Ian are consistent - let's say that actual rating satisfies them all.

To start working on the first draft of the future article, Irene needs to see at least some approximation to the actual rating. She asked you to find a proposal of a rating in which at least half of the triples known by Irene are satisfied.

Input data

The first line contains integers n and m (3n10^5, 1m10^5), the number of rated universities, and the number of triples given to Irene by Ian.

Each of the next m lines contains three distinct integers (1a[i], b[i], c[i]n) - the universities making a triple.

Output data

Output the proposal of a rating from the first university to the last one. The proposal rating should satisfy at least m / 2 triples. If there are many such proposals, output any one of them.

Example

In the example, the first two triples are satisfied whereas the last one is not. Therefore, at least half of all triples are satisfied.

Examples

Input example #1
4 3
1 2 3
1 2 3
1 4 3
Output example #1
4 3 2 1
Source 2015 ACM NEERC, Northern Subregion, October 24, Problem I