Xarxa social P81478

Ens donen la informació d’una xarxa social a on cada usuari es pot subscriure al contingut que publiquen altres usuaris. La relació de subscripció no és recíproca, és a dir, l’usuari "toni" pot estar subscrit al contingut de l’usuari "marc" però en "marc" pot no tenir subscripció a "toni".

Per tal de fer certs estudis sobre les relacions de subscripció, ens interessa saber, donat un usuari de la xarxa, quants usuaris estan a distància k d’ell. Per exemple, si en "toni" està subscrit al "marc" i a la "sandra", tindrà dos usuaris a distància 1 d’ell. Si en "marc" està subscrit a l’"anna" i a la "sara", i la "sandra" al "toni", llavors en "toni" té dos usuaris a distància 2 (l’"anna" i la "sara").

Per defecte es considera que un usuari està a distància 0 d’ell mateix.

Entrada

L’entrada comença amb la descripció de la xarxa social. Aquesta descripció és la següent. Primer, s’indica el número d’usuaris n > 0 seguit del número de subscripcions m >= 0. A continuació segueix una seqüència amb n noms d’usuari i acaba amb una seqüència de m parells de noms d’usuari a on el primer nom del parell indica que està subscrit al seu segon nom.

A la descripció de la xarxa social segueix una seqüència S de parells nom d’usuari u, distància k.

Sortida

Per cada parell (u, k) de la seqüència S, s’ha d’escriure quants usuaris estan a distància k de l’usuari u.