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

Poveste şi cerinţă...

După ce a văzut cât de impresionaţi au fost toţi atunci când s-a transformat în murătură, Rick s-a hotărât să creeze un device că să se poată transforma în mai multe obiecte, legume sau specii de extratereştrii cât mai diverse.
 
Totuşi, el are anumite restricţii în ceea ce priveşte felul în care poate construi device-ul. Mai exact, el cunoaşte un număr $N$ şi $Q$ intervale: $(L{~i~},R{~i~})$ care au proprietatea că $L{~i~} &le; L{~i+1~}$ şi $R{~i~} &le; R{~i+1~}$ pentru orice i < Q.
Când programează device-ul, el trebuie să îi dea cel mult 4 * N + 2 * Q instrucţiuni de forma "x y" (fără ghilimele), însemnând că dacă el la un moment dat este obiectul, leguma, specia cu numărul $x$, se poate transforma în cea cu numărul $y$. Transformarea este una unidirecţionala, adică din starea $x$ nu se poate "reîntoarce" direct în $y$ decât dacă există şi instrucţiunea "y x".
 
Rick va considera că device-ul este bine făcut dacă există o modalitate să ajungă din starea cu numărul y (N + 1 &le; y &le; N + Q) în cea cu numărul $x$ (1 &le; x &le; N) dacă şi numai dacă $L{~y-N~} &le; x &le; R{~y-N~}$

h2. Date de intrare

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

Prima linie a fişierului de intrare $transform.in$ contine numerele $N$ şi $Q$. Pe următoarele $Q$ linii apar câte două numere, pe linia $i$ apărând $L{~i~}$ si $R{~i~}$.

h2. Date de ieşire

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

Pe prima linie a fişierului $transform.out$ se va afişa numărul de instrucţiuni pe care Rick le va programa în device-ul lui, fie $M$ numărul lor. Apoi, pe fiecare dintre următoarele $M$ linii se vor afişa câte două numere $x$ şi $y$, însemnând că din starea cu numărul x se poate trece în cea cu numărul $y$.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $0 ≤ N ≤ 1.000$
* $0 ≤ Q ≤ 2.000$
* $1 ≤ L{~i~} ≤ R{~i~} ≤ N$
* Rick poate să folosească la programarea device-ului său doar stări cuprinse între $1$ şi $10.000$.
* Dacă rezolvaţi cu maxim $2N + 2QlogN$ muchii atunci veţi primi 40% din punctaj, dacă rezolvaţi cu maxim $4N + 2Q$ muchii veţi primi 100% din punctaj.
 
h2. Subtaskuri
 
* *$Subtaskul 1 (25 de puncte):$* Toate intervalele sunt fie prefixe fie sufixe.
* *$Subtaskul 2 (25 de puncte):$* Toate intervalele au cel o poziţie comună.
* *$Subtaskul 3 (50 de puncte):$* Fără restricţii suplimentare.
 
 

h2. Exemplu
table(example). |_. transform3.in |_. transform3.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 4 3
  1 3
  2 3
  3 4
| 7
  5 1
  5 8
  8 2
  8 3
  6 8
  7 3
  7 4

|
h3. Explicaţie

...

În exemplul pe care Rick vi-l arată, el se foloseşte de starea 8, pentru a reduce complexitatea device-ului. Într-adevăr, pentru fiecare stare din cele Q se poate ajunge strict la intervalul de stări specificat în fişierul de intrare. Device-ul fiind creat de el, acesta este evident bine făcut.

== include(page="template/taskfooter" task_id="transform3") ==