Problems Base course RU

The comparison log

A program sorted n distinct numbers and wrote every comparison it made into a log: “number a is less than number b”. The numbers are labelled 1 to n, the values themselves are lost, and so are some log entries. Can the order of all n numbers be recovered from the remaining entries?

If so, print YES and the labels of the numbers in increasing order. If not, print NO and the labels of two numbers whose order cannot be established from the log: the entries do not imply that one is less than the other, even through a chain “a < c, c < b”. There may be several suitable pairs; any will do.

The logs in the tests are real: this is how merge sort, Python’s sorted, heapsort and quicksort compared when ordering the populations and latitudes of the world’s towns (GeoNames). In some tests some entries are erased.

In the first example 3 < 1, 1 < 4 and 4 < 2: the order 3, 1, 4, 2 is recorded in full. In the second it is known that 3 is less than both 1 and 4, and both of them are less than 2, but which of 1 and 4 is smaller is not recorded.

Input

The first line holds n and m (1 ≤ n ≤ 100,000, 0 ≤ m ≤ 200,000). Then m lines of two labels a and b (a ≠ b): number a is less than number b. The entries do not contradict each other; the same entry may occur several times.

Output

The first line holds YES or NO. The second holds, for YES, all n labels in increasing order of the numbers, and for NO, two labels whose order is unknown.

Examples

Example 1

Input

Output

YES
3 1 4 2

Example 2

Input

Output

NO
1 4

Limits

Time · Python: 4000 ms
Time · Go: 1500 ms
Memory: 256 MB
Judging: 14 tests

Walkthrough

Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.

1Hint 1

Picture the entries as arrows “smaller → larger”. Which number can be the smallest? And what if there are two such candidates?

2Hint 2

Only a number that no arrow enters can be the smallest. Remove it and repeat. What does it mean if at some point there are two such numbers?

3The idea

This is topological sorting by Kahn’s algorithm: keep the numbers that have no unaccounted “smaller” ones left, and remove them one at a time. If at some moment two numbers are ready, their order is unknown. Suppose these are u and v and the entries imply u < v, a chain u < … < w < v. All its links after u have not been removed yet, since u itself has not; so v still has an unaccounted arrow from w, and v could not have been ready. If only one number is ever ready, the order is unique: each next number must come right after the previous one.

4Walkthrough

For each number keep a list of “larger” ones and a counter of “smaller” ones. Put everyone with a zero counter into a queue; while the queue is not empty, if it holds more than one number, print NO and the first two; otherwise remove the number, append it to the answer, and decrement the counters of its “larger” ones. Repeated entries do no harm: each entry incremented a counter and will decrement it exactly once.

What this means for sorting. The order can be recovered if and only if each pair of neighbours in the final order has a direct entry. So any correct comparison sort must compare every pair of neighbours, and that is how the article proves the lower bounds for merging and for checking that all numbers are distinct. Entries about non-neighbours can be erased from the log at will; losing one entry about neighbours makes the order unknown. In the seventh test a hundred entries are erased from a merge sort log, and the order can be recovered; in the sixth one entry is, and it can no longer.

4+Solution

5Complexity

O(n + m) time and memory.

6Common mistakes

Looking only at the ends. If the smallest and largest numbers are unambiguous, the middle may still be unknown, as in the second example. This is wrong.py.
Counting entries. “There are at least n − 1 entries, so the order is known” is wrong: what matters is which pairs the entries are about, not how many there are.
Building the transitive closure. Checking all pairs for reachability is O(n·m), too slow for a hundred thousand numbers.

Algorithms behind it

SRT Technique Lower bounds for comparisons Why not faster: counting outcomes and playing against a judge; sorting, second in a tournament, minimum with maximum, merging. sorting needs ⌈log₂ n!⌉ comparisons 1 problem GRA Algorithm Topological sort Lines up the vertices of a graph without cycles so that all edges point forward, in O(V + E). O(V + E) 2 problems