P7871 "Wdoi-4" Flandre? M Q! The Sage and the Riddle

The background does not contain key information for solving the problem and can be skipped. --- Flandre Scarlet is a vampire who once lived in the basement of the Scarlet Devil Mansion. Unlike other vampires, Flandre has special wings made of colorful crystals, different from the bat-like wings of other vampires: crystals of different colors are lined up in order. The colors of the crystals on Flandre's wings from inner to outer are sky blue, blue, purple, pink, orange, yellow, light green, and sky blue. Therefore, in fact, Flandre's wings are very likely composed of Patchouli's "Philosopher's Stone". But Flandre does not care about that. She only cares about the energy flow between the Philosopher's Stones arranged in the shape of wings: if a Philosopher's Stone is given energy, it will enter an excited state. An excited Philosopher's Stone is very unstable: the burst of its huge energy will affect surrounding Philosopher's Stones, causing energy transfer. Flandre finds this very interesting, and made a riddle to test Patchouli. But as a sage, Patchouli does not want to think and just wants to slack off, so the task is handed to you! 

Flandre got $n$ Philosopher's Stones from Patchouli and lined them up from left to right in a row. Patchouli can assign each Philosopher's Stone an energy level, which determines how energy is transferred between stones. Note that **each energy level must be a positive integer, and no two Philosopher's Stones may have the same energy level**. If the $i$-th Philosopher's Stone is energized (enters the excited state), it will pass energy to the one with the **smaller energy level** among the $(i-1)$-th and $(i+1)$-th stones. In particular, if a stone has only one neighbor, it will only send energy to that neighbor. Note that even if the $i$-th stone's energy level is lower than both the $(i-1)$-th and $(i+1)$-th stones, it **can still transmit energy**. Now Flandre has $q$ conditions: each condition gives two positive integers $s,t$, meaning that if Flandre activates the energy of the $s$-th Philosopher's Stone, then the energy will eventually pass through the $t$-th stone. However, since Patchouli has asthma, setting the energy levels is very tiring. Therefore, if there exists a legal assignment of energy levels, please find the **lexicographically smallest** one. For two assignments $A,B$, we say $A$ is lexicographically smaller than $B$ if and only if there exists a $p$ such that $\forall i

The first line contains two integers $n,q$, representing the number of Philosopher's Stones and the number of Flandre's conditions. The next $q$ lines each contain two integers $s_i,t_i$, describing one condition.

If no legal assignment exists, output `QED`. Otherwise output $n$ integers, representing the lexicographically smallest assignment.

Input/output sample $2$ can be found in the attached files $\textbf{\textit{qed2.in}/\textit{qed2.out}}$. Input/output sample $3$ can be found in the attached files $\textbf{\textit{qed3.in}/\textit{qed3.out}}$. --- ### Constraints and Notes For $100\%$ of the testdata, $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{Test Point} & \bm{n\le} & \bm{q\le} & \textbf{Special Constraint} \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}$$ Translated by ChatGPT 5