Fişierul intrare/ieşire:	transform3.in, transform3.out	Sursă	Summer Challenge 2021
Autor	Alexandru Luchianov	Adăugată de	comisia summer 2k21 •summer21
Timp execuţie pe test	0.1 sec	Limită de memorie	131072 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Transform3

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 ≤ L_i+1 şi R_i ≤ 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 ≤ y ≤ N + Q) în cea cu numărul x (1 ≤ x ≤ N) dacă şi numai dacă L_y-N ≤ x ≤ R_y-N

Date de intrare

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.

Date de ieşire

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.

Restricţii

• 0 ≤ N ≤ 2.000
• 1 ≤ L_i ≤ R_i ≤ N
• 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ţ$
• Daca rezolvati cu maxim 2N + 2QlogN muchii atunci veti primi 70% din punctaj, daca rezolvati cu maxim 4N + 2Q muchii veti primi 100% din punctaj.

Subtaskuri

• Subtaskul 1 (25 de puncte): Toate intervalele sunt fie prefixe fie sufixe.
• Subtaskul 2 (25 de puncte): Toate intervalele au cel o pozitie comuna.
• Subtaskul 3 (50 de puncte): Fara restrictii suplimentare.

Exemplu

Explicaţie

...

Cum se trimit solutii?