Description

伊恩在一家评级机构工作，该机构发布最佳大学的评级。艾琳是一名记者，计划撰写一篇关于即将发布的评级的轰动性文章。

通过各种社会工程技术（我们不深入细节），艾琳从伊恩那里获得了一些内部信息。

具体来说，艾琳收到了几个三元组 $(a_{i}, b_{i}, c_{i})$，这意味着在即将发布的评级中，大学 $b_{i}$ 位于大学 $a_{i}$ 和 $c_{i}$ 之间。也就是说，要么 $a_{i}$ 在 $b_{i}$ 之前，$b_{i}$ 在 $c_{i}$ 之前，要么相反。伊恩提供的所有三元组都是一致的——假设实际评级满足它们。

为了开始撰写未来文章的初稿，艾琳需要看到至少某种对实际评级的近似。她要求你找到一个评级提案，其中至少有一半的艾琳已知的三元组得到满足。

Input Format

第一行包含整数 $n$ 和 $m$，分别表示被评级的大学数量和伊恩给艾琳的三元组数量 $(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)$。

Output Format

输出从第一所大学到最后一所大学的评级提案。该提案评级应满足至少 $m/2$ 个三元组。如果有多个这样的提案，输出其中任意一个。

4 3
1 2 3
1 2 3
1 4 3

4 3 2 1

Hint

时间限制：2 秒，内存限制：256 MB。

题面翻译由 ChatGPT-4o 提供。