Školsko natjecanje iz informatike 2017. / Srednja škola / Druga podskupina (3. i 4. razred) - 2. zadatak

Društvene mreže, osim mnoštva veselih korisnika, privlače i znanstvenike koji na razne načine pokušavaju analizirati dostupne podatke. Graf društvene mreže se sastoji n od korisnika od kojih su m parova korisnika označeni kao prijatelji. Relacija “biti prijatelj” je simetrična (ako je A prijatelj od B onda smatramo da je i B prijatelj od A). Svaki korisnik društvene mreže je jedinstveno određen imenom — nizom od najviše 10 malih slova engleske abecede. Trokut je neuređena trojka različitih korisnika A, B i C koji su svi međusobno prijatelji. Broj trokuta u nekoj zajednici korisnika je zanimljiv jer je iskustvo pokazalo da je pozitivno koreliran s duljinom postojanja zajednice — što dulje zajednica postoji, to će više ljudi upoznati svoje prijatelje koji se još ne poznaju te tako stvarati nove trokute. Zadana je jedna zajednica (skup korisnika) u društvenoj mreži. Potencijal korisnika A je broj koji definiramo na sljedeći način: pretpostavimo da svaka dva prijatelja od A, koji još nisu prijatelji međusobno, označimo kao prijatelje. Potencijal od A je ukupni broj trokuta u cijeloj zajednici nakon tog postupka. Odredite potencijal svakog korisnika u zajednici te ispišite korisnike, poredane abecedno po imenu, zajedno s njihovim potencijalima.

Ulazni podaci

U prvom redu nalaze se prirodni brojevi n i m (n ≤ 20, m ≤ 100) — broj korisnika u zajednici te broj prijateljstava. Svaki od sljedećih m redova sadrži dva različita imena ai i bi odvojena točno jednim razmakom koji označavaju su korisnici ai i bi prijatelji. Svako ime je niz od najmanje jednog i najviše 10 malih slova engleske abecede. Svaki od n korisnika sudjeluje u barem jednom prijateljstvu. Niti jedno prijateljstvo se ne pojavljuje više puta na ulazu.

Izlazni podaci

Ispišite n redova. U svaki od redova ispišite ime odgovarajućeg korisnika te njegov potencijal odvojene jednim razmakom. Korisnici moraju biti sortirani po imenu uzlazno abecednim (rječničkim) poretkom.

Primjeri test podataka

ulaz

3 2
mark larry
larry john

izlaz

john 0
larry 1
mark 0

ulaz

6 7
mirko slavko
slavko janko
janko mirko
slavko luka
luka mirjana
mirjana ivana
ivana luka

izlaz

ivana 2
janko 2
luka 5
mirjana 2
mirko 2
slavko 5

ulaz

6 6
mirko ana
ana anamarija
anamarija marijana
marijana slavko
slavko janko
janko ana

izlaz

ana 4
anamarija 1
janko 1
marijana 1
mirko 0
slavko 1