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.
Input
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
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 |
Yes |
Sample Input 2 | Sample Output 2 |
---|---|
5 4 1 4 2 3 4 5 1 5 |
No |