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 y nu se poate "reîntoarce" direct în x decât dacă există şi instrucţiunea "y x".

Rick va consideră că device-ul este bine făcut dacă există o modalitate să ajungă din starea cu numărul x (1 ≤ x ≤ N) în cea cu numărul y (N + 1 ≤ y ≤  N + Q) dacă şi numai dacă l[y – N] ≤ x ≤ r[y – N]

Rick va considera că device-ul este bine făcut dacă există o modalitate să ajungă din starea cu numărul x (1 ≤ x ≤ N) în cea cu numărul y (N + 1 ≤ y ≤  N + Q) dacă şi numai dacă l[y – N] ≤ x ≤ r[y – N]

h2. Date de intrare

h2. Date de ieşire

Pe prima linie a fişierului $transform.out$ se va afişa numarul de instructiuni pe care Rick le va programa in device-ul lui, fie M numarul lor. Apoi, pe fiecare dintre urmatoarele M linii se vor afisa cate doua numere x si y, insemnand ca din starea cu numarul x se poate trece in cea cu numarul y.

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 ≤ 10^6^$
* $1 ≤ l[i] ≤ r[i] ≤ N$

* Rick nu este obligat sa foloseasca la programarea device-ului sau doar stari cuprinse intre 1 si N + Q, el se poate folosi de stari intermediare oricat de diverse, atata vreme cat in final este respectata conditia din enunt$
* Pentru teste in valoare $
* Pentru alte teste in valoare de$
* Pentru alte teste in valoare de$
* Pentru alte teste in valoare de  nu există restricţii suplimentare

* Rick nu este obligat să folosească la programarea device-ului său doar stări cuprinse între 1 şi N + Q, el se poate folosi de stări intermediare oricât de diverse, atâta vreme cât în final este respectată condiţia din enunţ$
* Pentru teste în valoare $
* Pentru alte teste în valoare de$
* Pentru alte teste în valoare de$
* Pentru alte teste în valoare de  nu există restricţii suplimentare

h2. Exemplu