permking

Permking

== include(page="template/taskheader" task_id="permking") ==

Poveste şi cerinţă...

Regele permutarilor a dat zvon in toata tara si si-a facut cunoscuta intreaga putere: "Mie nu imi e frica decat de propria-mi putere!!!"
 
Fie o permutare $P$ de lungime $N$. Asupra acestei permutari se executa $M$ operatii de tipul $a, b$: sorteaza in ordine crescatoare toate elementele din intervalul $[a,b]$. La finalul celor $M$ operatii, permutarea este considerata sortata daca toate elementele apar in ordine strict crescatoare (ramane exercitiu de imaginatie cum arata o permutare sortata).
 
Dandu-se $M$ si cele $M$ operatii, sa se raspunda cu $1$ daca operatiile sunt suficiente sa sorteze ORICE permutare $P$ existenta de lungime $N$ si cu $0$ daca nu.

h2. Date de intrare

Fişierul de intrare $permking.in$ ...

Fişierul de intrare $permking.in$ va contine un numar natural $T$ reprezentand numarul de teste. Pe urmatoarele linii sunt cele $T$ teste in urmatorul format: pe prima linie se afla $2$ numere naturale $N$ si $M$. Pe urmatoarele $M$ linii sunt cate $2$ numere naturale $a, b$ reprezentand cele $M$ operatii.

h2. Date de ieşire

În fişierul de ieşire $permking.out$ ...

Fişierul de ieşire $permking.out$ va contine $T$ linii, pe linia $x$ aflandu-se raspunsul pentru testul $i$ ({$0$} sau $1$).

h2. Restricţii
* $1 ≤ T ≤ 20$
* $1 ≤ N, M ≤ 1000$

* $1 ≤ a ≤ b ≤ N$

h2. Exemplu