Insider's Information

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

Irene used a few social engineering tricks (let us skip the details) and got some insider's information from Ian.

She received several triples $(a_i, b_i, c_i)$ of university numbers. Each triple means that in the upcoming rating university $b_i$ stands between universities $a_i$ and $c_i$: either $a_i$ comes before $b_i$ and $b_i$ comes before $c_i$, or the other way round. Every triple Ian told her agrees with the actual rating, and the actual rating satisfies all of them.

To start the first draft of the article, Irene needs a proposal that is at least close to the actual rating. Find a proposal that satisfies at least half of the triples. Many proposals do that, so print the one built by the procedure given in the output section.

The first line contains two integers $n$ and $m$, the number of rated universities and the number of triples Ian gave to Irene ($3 \le n \le 100000$; $1 \le m \le 100000$).

Each of the next $m$ lines contains three distinct integers $a_i$, $b_i$ and $c_i$, the universities of one triple ($1 \le a_i, b_i, c_i \le n$). At least one rating satisfies all $m$ triples.

Print the university numbers from the first place to the last place in one line, separated by single spaces.

Several proposals satisfy at least half of the triples, so print exactly the one that the following procedure builds.

Stage 1, the removal order. Every triple starts alive. In a triple $(a, b, c)$ call $b$ the middle university and call $a$ and $c$ the end universities. A university is free when it is the middle university of no living triple. Repeat $n$ times: among the universities that are still present, remove the free one with the smallest number. The universities get removal ranks $1$ to $n$ in the order in which they are removed. When a university is removed, every living triple that has it as an end university dies. The guarantee on the input makes a free university exist at every step.

Stage 2, the placement. Place the universities in the reverse order of removal, from rank $n$ down to rank $1$. The university of rank $n$ alone is the starting sequence. The university $u$ of rank $i$ goes either to the front or to the back of the sequence built so far. Look only at the triples whose three universities all have removal rank at least $i$. In such a triple $u$ is an end university. Write $w$ for its middle university and $v$ for its other end university. Putting $u$ at the front satisfies the triple when $w$ stands before $v$ in the current sequence, and putting $u$ at the back satisfies it when $v$ stands before $w$. Count the triples that each of the two options satisfies and take the option with the larger count. When the two counts are equal, put $u$ at the front.

The proposal built this way always satisfies at least $m/2$ triples.

The university that comes first in the actual rating is the middle university of no triple. The same holds inside the set of universities that are still present, so stage 1 never gets stuck.

In stage 2 a triple is judged once, at the step that places the university with the smallest removal rank among its three, and that university is an end university of the triple. One of the two options, front or back, satisfies the triple, so the option with the larger count satisfies at least half of the triples judged at that step. Adding up all steps gives at least $m/2$.