Problem E
Swap to Sort

You are given an array $A[1...N]$ with integers in decreasing order and a list of pairs $(a_1, b_1)$, $(a_2, b_2),$ $\ldots $, $(a_ K, b_ K)$. You wish to sort the array $A$ in increasing order, each turn you choose an $i$ ($i$ can be chosen multiple times) and swap $A[a_ i]$ with $A[b_ i]$. Determine whether this is possible.


The first line contains two integers, representing $N$ and $K$ respectively ($1 \leq N, K \leq 10^6$). The following $K$ lines each contains two integers, representing $a_ i$ and $b_ i$ respectively ($1 \leq a_ i < b_ i \leq N$).


Output “Yes” if it is possible to sort the array in increasing order, “No” otherwise.

Sample Input 1 Sample Output 1
5 2
1 5
2 4

Sample Input 2 Sample Output 2
5 4
1 4
2 3
4 5
1 5

Please log in to submit a solution to this problem

Log in