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
1 ≤ M ≤ 2007
0 ≤ K ≤ 100000
Numărul de produse determinat trebuie să fie cel mult egal cu 2*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.