TheForces Round #17 (AOE-Forces) |
---|
Finished |
Akbar wants to send $$$n$$$ letters to $$$m$$$ companies.
First letter should be sent to $$$l_{1}{th}$$$ company, second letter should be sent to $$$l_{2}{th}$$$ company, ..... , $$$n_{th}$$$ letter should be sent to $$$l_{n}{th}$$$ company, in the other words, letter $$$i$$$ should be sent to $$$l_{i}{th}$$$ company, $$$(1 \le l_i \le m)$$$.
Akbar bought $$$n$$$ envelopes for sending these letters, and wrote the address of the $$$l_{i}{th}$$$ company on the $$$i_{th}$$$ letter.
Akbar tells Amir to put the $$$i_{th}$$$ letter in the $$$i_{th}$$$ envelope, But Amir wants to not carry out this order properly and ruin the work fundamentally. For this reason, he decided to put the letters in the envelopes in such a way that each envelope contains exactly one letter, but no company receives its own letter.
Now your task is to help Amir to check whether it is possible to do such a thing or not.
In the first line of input, you'll be given two positive integers $$$n$$$ and $$$m$$$.
$$$$$$1 \le m \le n \le 10^5$$$$$$
In the second line of input, you'll be given $$$n$$$ positive integers $$$l_1, l_2, ... , l_n$$$ separated by space, that $$$l_i$$$ shows the destination company of the $$$i_{th}$$$ letter.
$$$$$$1 \le l_i \le m$$$$$$
It's guaranteed that all numbers $$$1, 2, 3, .... , m$$$ have appeared at least once in this sequence.
If it is possible to put the letters in the envelopes so that no letter reaches the corresponding company, print "YES", otherwise print "NO".
3 1 1 1 1
NO
4 4 4 1 2 3
YES
Explanation of testcase $$$1$$$ :
All the letters are addressed to company $$$1$$$, so all the envelopes have the address of company $$$1$$$, so any permutation of the letters in the envelopes, all the letters will reach company $$$1$$$, and Amir will not reach his goal.
Explanation of testcase $$$2$$$ :
We have four letters for companies $$$1, 2, 3, 4$$$ and four envelopes with the addresses of companies $$$1, 2, 3, 4$$$. We put the letter of company $$$1$$$ in the envelope of company $$$2$$$ and the letter of company $$$2$$$ in the envelope of company $$$1$$$. Also, we put the letter of company $$$3$$$ in the envelope of company $$$4$$$ and the letter of company $$$4$$$ in the envelope of company $$$3$$$. In this way, no letter reaches the relevant company and Amir reaches his goal.
Name |
---|