Ian 在一家发布顶尖大学排名的评级机构工作。Irene 是一位记者，她计划撰写一篇关于即将发布的排名的丑闻文章。

通过各种社会工程学手段（细节暂且不表），Irene 从 Ian 那里获得了一些内幕消息。

具体来说，Irene 收到了若干个三元组 $(a_i, b_i, c_i)$，这意味着在即将发布的排名中，大学 $b_i$ 位于大学 $a_i$ 和 $c_i$ 之间。也就是说，要么 $a_i$ 排在 $b_i$ 前面且 $b_i$ 排在 $c_i$ 前面，要么顺序正好相反。Ian 提供的所有三元组都是一致的——假设实际的排名满足所有这些三元组。

为了开始撰写文章的初稿，Irene 需要看到对实际排名的一个近似。她请求你找出一个排名方案，使得她所知的至少一半的三元组得到满足。

输入格式

第一行包含整数 $n$ 和 $m$，分别表示参与排名的大学数量和 Irene 从 Ian 那里得到的三元组数量（$3 \le n \le 100\,000$；$1 \le m \le 100\,000$）。

接下来的 $m$ 行，每行包含三个不同的整数 $a_i, b_i, c_i$，表示构成一个三元组的大学（$1 \le a_i, b_i, c_i \le n$）。

输出格式

输出一个从第一所大学到最后一所大学的排名方案。该排名方案应满足至少 $\frac{m}{2}$ 个三元组。如果存在多个这样的方案，输出其中任意一个即可。

样例

样例输入 1

4 3
1 2 3
1 2 3
1 4 3

样例输出 1

4 3 2 1

说明

在上面的例子中，前两个三元组得到了满足，而最后一个没有。因此，至少有一半的三元组得到了满足。