Zadanie

Gabriel Murár

Počet bodov: 45, časový limit: 1000ms

Gabo je murárom. Od svojho nadriadeného dostal za úlohu namaľovať múr dĺžky \(n\) postupne \(f\) farbami. Konkrétnejšie, dostal zoznam príkazov nasledovného formátu:

Vo všetkých príkazoch platí \(l_i \leq r_i\).

Nadriadený sa prišiel pozrieť na výsledok Gabovej práce a nepáčil sa mu. Niečo bolo určite zle, ale nevedel povedať, čo. Zoznam príkazov, ktoré dal Gabovi, bohužiaľ stratil, no možno ho nebude potrebovať na to, aby zistil, že naozaj nastala chyba. A potom to Gabovi poriadne vytmaví.

Úloha

Výsledný múr si môžeme predstaviť ako rad čísel dĺžky \(n\), kde \(i\)-te číslo je farba múru na pozícii \(i\). Dostanete popis múru a počet farieb \(f\), ktoré mali byť použité počas maľovania. Rozhodnite, či existuje zoznam príkazov, ktorých vykonaním by sme dosiahli daný výsledok.

Vstup

Vstup pozostáva z niekoľkých testovacích prípadov. Na prvom riadku vstupu sa nachádza počet týchto prípadov \(t\), platí \(1 \leq t \leq 20\,000\).

Nasleduje popis každého z \(t\) prípadov, každý začína prázdnym riadkom. Na ďalšom riadku sú dve celé čísla \(n, f\) oddelené medzerou – dĺžka múru a počet farieb. Platí \(1 \leq f \leq n \leq 100\,000\).

Na ďalšom riadku je \(n\) medzerou oddelených celých čísel v rozsahu od \(1\) po \(f\): farba múru na pozíciách \(1, 2, ..., n\).

Súčet \(n\) vo všetkých testovacích prípadoch nepresiahne \(200\,000\).

Výstup

Pre každý testovací prípad vypíšte na samostatný riadok ano, ak sme výsledok mohli dosiahnuť nejakým zoznamom príkazov, inak vypíšte nie.

Príklad

Input:

3

4 2
1 2 1 2

4 2
2 1 1 2

6 4
1 2 3 2 4 1

Output:

nie
nie
ano

Všimnite si, že v druhom prípade je odpoveď nie. To preto, lebo v zozname príkazov musia byť farby použite v poradí podľa ich čísla. Ak by to tak nemuselo byť, tak zoznam farbou 2 od 1 po 4, farbou 1 od 2 po 3 by vyhovoval.

Pre odovzdávanie sa musíš prihlásiť.