Xarxa social P81478


Statement
 

pdf   zip

thehtml

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.

Public test cases
  • Input

    6 8
    toni marc sandra sara anna sergi
    toni marc
    toni sandra
    sergi sandra
    marc anna
    sergi anna
    marc sara
    sandra toni
    sara sergi
    
    toni 0
    toni 1
    toni 2
    toni 3
    toni 4
    anna 0
    anna 1
    anna 2
    sara 2
    marc 1
    marc 2
    marc 3
    marc 4

    Output

    1
    2
    2
    1
    0
    1
    0
    0
    2
    2
    1
    1
    1
    
  • Input

    4 0
    a b c d
    
    a 0
    b 0
    c 0
    d 0
    a 1
    b 1
    c 1
    d 1

    Output

    1
    1
    1
    1
    0
    0
    0
    0
    
  • Information
    Author
    Emma Rollon
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++ Python