Fişierul intrare/ieşire:promo.in, promo.outSursăBaraj ONI 2007
AutorMugurel Ionut AndreicaAdăugată deDITzoneCAdrian Diaconu •DITzoneC
Timp execuţie pe test0.175 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Promo

Compania ONIx comercializeaza N produse. Pentru a creste vanzarile, compania a pus la dispozitia clientilor M oferte promotionale. Fiecare oferta consta din exact 2 produse diferite, care sunt vandute impreuna la un pret mai scazut decat daca ar fi vandute separat (de exemplu, suc si apa minerala). Produsele sunt identificate prin numere de la 1 la N, iar ofertele promotionale prin numere de la 1 la M. Deoarece si-au schimbat de curand aplicatia software ce gestioneaza baza de date a companiei, angajatii nu s-au obisnuit cu noul sistem si, din neatentie, unul dintre acestia a sters toate informatiile despre produsele si ofertele existente. Singurele informatii ramase sunt cele ale departamentului de statistica, care foloseste o baza de date proprie. Aceste informatii sunt reprezentate de numarul M de oferte si de toate cele K perechi de oferte ce au un produs in comun (in mod evident, oricare 2 oferte pot avea cel mult un produs in comun).

Cerinta

Folosind informatiile departamentului de statistica, determinati numarul de produse si cele 2 produse din cadrul fiecarei oferte.

Date de intrare

Prima linie a fisierului de intrare promo.in contine numerele intregi M si K, separate printr-un spatiu. Urmatoarele K linii contin cate 2 numere intregi A si B, separate printr-un spatiu, avand semnificatia ca oferta cu numarul A si cea cu numarul B au un produs in comun.

Date de iesire

Pe prima linie a fisierului de iesire promo.out veti afisa numarul intreg N, reprezentand numarul de produse. Urmatoarele M linii trebuie sa contina cate 2 numere intregi, separate printr-un spatiu. A i-a linie dintre aceste M linii va contine numerele produselor din care este formata a i-a oferta.

Restrictii

  • 1 ≤ M ≤ 2007
  • 0 ≤ K ≤ 100 000
  • Numarul de produse determinat trebuie sa fie cel mult egal cu 2*M.
  • Se garanteaza existenta cel putin a unei solutii. Daca exista mai multe solutii, puteti afisa oricare dintre ele.

Exemplu

promo.inpromo.out
11 7
1 4
4 7
7 1
2 5
5 8
8 2
10 11
17
1 2
3 4
5 6
1 7
3 8
9 10
1 11
3 12
13 14
15 16
15 17
5 7
1 2
1 3
1 4
1 5
2 3
2 4
3 5
5
1 2
2 3
1 3
2 4
1 5
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content