Els amics dels meus amics són els meus amics (2) P43272

En una coneguda xarxa social propietat d’un tendre empresari, els usuaris estableixen relacions d’amistat simètriques. Donada una xarxa social, es vol saber quants amics tenen certs usuaris fent servir allò de "els amics dels meus amics són els meus amics".

Entrada

L’entrada consta de quatres parts: La primera conté dos nombres naturals n i m que corres­ponen al nombre d’usuaris a la xarxa i el nombre de relacions d’amistat directes entre ells. La segona part és una llista de n paraules que corresponen als n noms d’usuari. La tercera part conté la descripció de les relacions d’amistat directes: Per a cadascuna de les m relacions hi ha un parell de noms d’usuari x i y que indiquen que x i y són amics directes a la xarxa. L’ordre de les relacions d’amistats i dels parells no està prescrit, però tots són noms vàlids i cap usuari és amic de sí mateix. Finalment, a la quarta part de l’entrada hi ha una seqüència de noms d’usuaris.

Sortida

Per a cada nom d’usuari u a la quarta part de l’entrada, cal escriure el nombre total d’amics d’u i d’amics d’amics d’u (tret d’ell mateix i sense repetits).