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