题目描述
你需要构造一个长为 $1\sim n$ 的排列 $p$。
有 $m$ 个奖励，每个奖励形如 $(a,b,c)$，表示若 $p_b$ 处于 $p_a$ 与 $p_c$ 之间，即 $p_a< p_b< p_c$ 或 $p_c< p_b< p_a$，则获得 $1$ 收益。
你的方案需要使得收益 $\ge \lceil \frac m2\rceil$。
注意：数据保证存在收益 $=m$ 的方案。
输入格式
第一行两个整数 $n,m$。
接下来 $m$ 行，每行三个整数，表示 $a,b,c$。
输出格式
一行 $n$ 个整数，表示你构造的排列。只需要满足收益 $\ge \lceil \frac m2\rceil$ 则被判为正确。
样例
样例 $1$ 输入
6 3
2 4 3
4 1 3
2 1 5样例 $1$ 输出
3 1 5 2 4 6样例 $2$
见下发文件 $\text{ex\_construct2.in}$ 和 $\text{ex\_construct2.ans}$。
数据范围
对于所有数据，有 $n\le 10^5,m\le 10^5$。
- Subtask 1 (10 points)：$n\le 10$。
- Subtask 2 (10 points)：$c=1$。
- Subtask 3 (10 points)：$n\le 20$，$m\le 50$。
- Subtask 4 (10 points)：$n\le 20$。
- Subtask 5 (10 points)：$m\le 10$。
- Subtask 6 (50 points)：无特殊性质。