题目背景

题目背景不包含解题的关键信息，可以跳过。

---

芙兰朵露·斯卡蕾特是曾居住在红魔馆地下室的吸血鬼。与众不同的是，芙兰朵露有着彩色结晶的特殊翅膀，与其他吸血鬼蝙蝠一般的翅膀不同：颜色各异的结晶按照顺序一字排开。

芙兰朵露翅膀的彩色结晶的颜色从内到外分别是天蓝、蓝、紫、粉、橙、黄、淡绿和天蓝。因此事实上，芙兰朵露的翅膀很可能就是帕秋莉的「贤者之石」组成的。

但是芙兰朵露并不关心这些，她只关心排列成翅膀形状的贤者之石之间发生的能量流动——如果一块贤者之石被赋予了能量，就会处于激发态。处于激发态的贤者之石很不稳定——它大量能量的爆发会波及周围的贤者之石，以造成能量的转移。

芙兰朵露非常感兴趣，并以此出了一个谜题来考考帕秋莉。但是作为贤者的帕秋莉不想思考只想摸鱼，于是任务就交给你啦！

题目描述

芙兰朵露从帕秋莉那里搞来了 $n$ 块贤者之石，并从左往右排成了一列。帕秋莉可以赋予每块贤者之石一定的能级，这会决定贤者之石之间能量的传递。值得注意的是，能级必须要是正整数，并且不能有两块贤者之石能级相同。

如果第 $i$ 块贤者之石被赋予了能量（处于激发态），它就会将能量传递给第 $i-1$ 和第 $i+1$ 块里能级较小的那一块。特别地，如果某块贤者之石周围只有一块，那么它只会向这一块发送能量。注意，即使第 $i$ 块的能级低于第 $i-1$ 和第 $i+1$ 块，它照样可以传输能量。

现在芙兰有 $q$ 个条件——每个条件给定两个正整数 $s,t$，表示如果芙兰激活了第 $s$ 块贤者之石的能量，那么能量最终会经过第 $t$ 块。

然而由于帕秋莉有哮喘的老毛病，设定贤者之石的能级是很费力的。因此，如果存在一种合法的赋予贤者之石能级的方案，请你找出其中字典序最小的那个方案。对于两种方案 $A,B$，我们称 $A$ 的字典序小于 $B$，当且仅当存在一个 $p$，使得 $\forall i<p$ 有 $A_i=B_i$，且 $A_p<B_p$。

如果存在合法方案，请你输出字典序最小的方案；否则输出 QED。

输入格式

第一行有两个整数 $n,q$，表示贤者之石的块数和芙兰的条件个数。
接下来 $q$ 行，每行有两个整数 $s_i,t_i$，描述一组条件。

输出格式

若不存在合法方案，输出 QED；否则输出 $n$ 个整数，表示字典序最小的那个方案。

10 4
1 2
3 7
8 10
5 6

1 4 8 3 7 2 6 10 5 9

提示

输入/输出样例 $2$ 见下发的附件 $\textbf{\textit{qed2.in}/\textit{qed2.out}}$。

输入/输出样例 $3$ 见下发的附件 $\textbf{\textit{qed3.in}/\textit{qed3.out}}$。

---

数据范围及约定

对于 $100\%$ 的数据，$0\le q \le 3\times 10^5$，$3\le n \le 3\times 10^5$，$1\le s_i,t_i \le n$。

$$\def{\arraystretch}{1.5} \begin{array}{|c|c|c|c|} \hline \textbf{测试点} & \bm{n\le} & \bm{q\le} & \textbf{特殊限制} \cr \hline 1\sim 3 & 7 & 7 & - \cr \hline 4\sim6 & 100 & 100 & - \cr \hline 7 & 10^5 & 1 & -\cr \hline 8\sim 10 & 3\times 10^5 & 3\times 10^5 & s_i\le t_i \cr \hline 11\sim 12 & 10^5 & 10 & - \cr \hline 13\sim 20 & 3\times 10^5 & 3\times 10^5 & -\cr \hline \end{array}$$