promo

Promo

== include(page="template/taskheader" task_id="promo") ==

Poveste si cerinta...

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).
 
h2. Cerinta
 
Folosind informatiile departamentului de statistica, determinati numarul de produse si cele 2 produse din cadrul fiecarei oferte.

h2. 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.

h2. 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.

h2. 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.

h2. Exemplu
table(example). |_. promo.in |_. promo.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 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

|

 
h3. Explicatie
 
...

| 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
|

== include(page="template/taskfooter" task_id="promo") ==

== SmfTopic(topic_id="...") ==

1845