Energy Transmission of the Philosopher's Stones

Flan managed to get n Philosopher's Stones and arranged them in a row from left to right. Each stone is assigned a distinct positive integer energy level. When the i-th stone is activated, it will transmit its energy to the adjacent stone (either the stone to its left or right) which has the smaller energy level. In particular, if a stone has only one neighbor, it transmits energy only to that neighbor. Note that even if a stone’s energy level is lower than those of both its neighbors, it still transmits energy.

You are given q conditions. Each condition consists of two positive integers s and t, meaning that if the s-th stone is activated, then along the unique transmission process the energy will eventually pass through the t-th stone.

Your task is to assign the energy levels by choosing a permutation of the numbers {1, 2, …, n} so that all of the q conditions are satisfied. If there are multiple valid assignments, output the lexicographically smallest one. Here, a permutation A is lexicographically smaller than B if there exists an index p such that for all indices i < p we have A_i = B_i and A_p < B_p.

If no valid assignment exists, output QED.

inputFormat

The first line contains two integers n and q – the number of stones and the number of conditions respectively.

Each of the following q lines contains two integers s and t, representing a condition that if the s-th stone is activated, the energy must eventually pass through the t-th stone.

outputFormat

If a valid assignment exists, output the lexicographically smallest permutation of the numbers from 1 to n (with a single space separating consecutive numbers). Otherwise, output QED.

sample

5 3
3 1
1 2
5 3

1 2 3 4 5