promo

Compania ONIx comercializează $N$ produse. Pentru a creşte vânzările, compania a pus la dispoziţia clienţilor $M$ oferte promoţionale. Fiecare ofertă constă din exact $2$ produse diferite, care sunt vândute împreună la un preţ mai scăzut decât dacă ar fi vândute separat (de exemplu, suc şi apă minerală). Produsele sunt identificate prin numere de la $1$ la $N$, iar ofertele promoţionale prin numere de la $1$ la $M$. Deoarece şi-au schimbat de curând aplicaţia software ce gestionează baza de date a companiei, angajaţii nu s-au obişnuit cu noul sistem şi, din neatenţie, unul dintre aceştia a şters toate informaţiile despre produsele şi ofertele existente. Singurele informaţii rămase sunt cele ale departamentului de statistică, care foloseşte o bază de date proprie. Aceste informaţii sunt reprezentate de numărul $M$ de oferte şi de toate cele $K$ perechi de oferte ce au un produs în comun (în mod evident, oricare $2$ oferte pot avea cel mult un produs în comun).

Cerinţă

Folosind informaţiile departamentului de statistică, determinaţi numărul de produse şi cele $2$ produse din cadrul fiecărei oferte.

Date de intrare

Prima linie a fişierului de intrare promo.in conţine numerele întregi $M$ şi $K$, separate printr-un spaţiu. Următoarele $K$ linii conţin câte $2$ numere întregi $A$ şi $B$, separate printr-un spatiu, având semnificaţia că oferta cu numărul $A$ şi cea cu numărul $B$ au un produs în comun.

Date de ieşire

Pe prima linie a fişierului de ieşire promo.out veţi afişa numărul întreg $N$, reprezentând numărul de produse. Următoarele $M$ linii trebuie să conţină câte $2$ numere întregi, separate printr-un spaţiu. A $i$-a linie dintre aceste $M$ linii va conţine numerele produselor din care este formată a $i$-a ofertă.

Restricţii si precizări

• $1 \leq M \leq 2 \ 007$
• $0 \leq K \leq 100 \ 000$
• Numărul de produse determinat trebuie să fie cel mult egal cu $2 \cdot M$.
• Se garantează existenţa cel puţin a unei soluţii. Dacă există mai multe soluţii, puteţi afişa oricare dintre ele.

Exemplu

promo.in

11 7
1 4
4 7
7 1
2 5
5 8
8 2
10 11

promo.out

17
1 2
3 4
5 6
1 7
3 8
9 10
1 11
3 12
13 14
15 16
15 17