Friend of Friend

fof

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

In reteaua de socializare hi6 fiecaruia dintre cei $N$ utilizatori ii este asociat un id sub forma unui numar intreg. Spunem ca doi utilizatori sunt prieteni daca intre ei exista o relatie de prietenie in reteaua de socializare. Pentru a creste popularitatea retelei de socializare si a creste interactiunea utilizatorilor trebuie sa implementam un sistem prin care unui utilizator ii este afisata o lista de persoane pe care este foarte probabil sa le cunoasca si care ii sunt sugerate sprea adaugare la prieteni. Primul pas pentru a reusi acest lucru este de a genera pentru fiecare utilizator lista de persoane cu care nu este prieten, dar cu care are macar un prieten comun.

Poveste şi cerinţă...

h2. Date de intrare

Fişierul de intrare $fof.in$ contine pe prima linie doua numere naturale $N$ si $M$, reprezentand numarul de utilizatori, respectiv numarul de relatii de prietenie din reteaua hi6. Pe urmatoarele $M$ numere sunt definite relatiile de prietenie, cate una pe linie, sub forma unei perechi de id-uri.

Fişierul de intrare $fof.in$ ...

h2. Date de ieşire

În fişierul de ieşire $fof.out$ va contine $N$ linii. Pe linia $i, (1 ≤ i ≤ N)$ se va afisa lista de sugestii generata pentru utilizatorul care are id-ul $i$. Lista afisata va fi sortata descrescator dupa numarul de prieteni comuni, iar in caz de egalitate crescator dupa id.

În fişierul de ieşire $fof.out$ ...

h2. Restricţii

* $1 ≤ N ≤ 1000$
* $1 ≤ M ≤ 5000$
* Toate id-urile sunt numere naturale distincte intre $1$ si $N$

* $... ≤ ... ≤ ...$

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

| 3 2
2 1
2 3
| 3
 
1

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

|

h3. Explicaţie
 
...

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

9718