Description

芙兰朵露从帕秋莉那里搞来了 $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。

Input Format

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

Output Format

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

10 4
1 2
3 7
8 10
5 6

1 4 8 3 7 2 6 10 5 9

Hint

输入/输出样例 $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}$$