MOG
Spanish
|
English

Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana

MOG Training #4

Ended

I - Insider's Information

Languages: C, C++, Java, Haskell, Pascal, Python, JavaScript, Tiger, C#
Time & Memory limits: (details)

Ian works for a rating agency that publishes ratings of the best universities. Irene is a journalist who plans 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 \emph{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

The first line contains integers $n$ and $m$, the number of rated universities, and the number of triples given to Irene by Ian ($3 \le n \le 100\,000$; $1 \le m \le 100\,000$).

Each of the next $m$ lines contains three distinct integers $a_i, b_i, c_i$ — the universities making a triple ($1 \le a_i, b_i, c_i \le n$).

Output

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

Sample test(s)

Input
4 3 1 2 3 1 2 3 1 4 3
Output
4 3 2 1

Hints

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