Szolga
Egy számítógépes hálózat $N$ csomópontot tartalmaz. Azt mondjuk, hogy az $Y$ csomópont közvetlen szomszédja az $X$ csomópontnak, ha össze vannak kötve kétirányú adatátvitelt biztosító közvetlen vonallal. (Tehát, ha $Y$ szomszédja $X$-nek, akkor $X$ is szomszédja $Y$-nak.) Van $K$ darab csomópont, amelyek névfeloldó szolgáltatást tudnak adni. Ha egy csomópontban lévő gép névfeloldást kíván, akkor a kérését el kell juttatnia valamelyik kiszolgálóhoz. Ha valamelyik közvetlen szomszédja kiszolgáló, akkor a kérését ennek továbbítja, amelyik azt meg is válaszolja. Egyébként a kérést valamelyik közvetlen szomszédjának kell átadni, aki azt továbbítja, és így tovább, amíg a kérés valamelyik kiszolgálóhoz nem ér, aki megválaszolja, és visszaküldi a választ ugyanazon útvonalon, amelyiken érkezett. A válaszidőt az határozza meg, hogy hány csomóponton keresztül jut el a kérés a kiszolgálóhoz.
Feladat
Készíts programot (SZOLGA.PAS, ...), amely minden csomópontra kiszámítja, hogy a csomópont melyik közvetlen szomszédjának küldje a kérést, ha az a cél, hogy a legrövidebb időn belül megkapja a választ!
Bemenet
A SZOLGA.BE szöveges állomány első sorában a csomópontok $N$ $(1\leq N\leq 10000)$ száma, és a kiszolgálók $K$ $(1\leq K\leq 1000)$ száma van. A csomópontokat az $1,\ldots,N$ számokkal azonosítjuk. A második sor a $K$ kiszolgáló sorszámait tartalmazza egy-egy szóközzel elválasztva. A következő $N$ sor írja le a hálózatot. Az állomány $i+2$-edik sorában azok a csomópontok vannak felsorolva egy-egy szóközzel elválasztva és 0-val zárva, amelyek az $i$ csomópont közvetlen szomszédjai. A hálózat legfeljebb 100000 közvetlen vonalat tartalmaz.
Kimenet
A SZOLGA.KI szöveges állomány első sorába azt az $M$ számot kell írni, amelyre teljesül, hogy bármely csomópont kérése megválaszolható úgy, hogy legfeljebb $M$ csomóponton keresztül jut el a kérés valamely kiszolgálóhoz (beleértve a kiszolgálót, de nem számítva a kérést küldőt)! A következő $N$ sor mindegyikébe két számot kell írni, az $i+1$-edik sorban az első szám a legkevesebb csomópont száma, amelyen keresztülhalad az $i$-edik csomópont kérése! A második szám pedig annak a csomópontnak a sorszáma legyen, amelyiknek az $i$ csomópont a kérését továbbítja! A kiszolgálók esetén a 0 i számpár legyen kiírva! Ha nincs olyan útvonal, amelyen az $i$-edik csomópont eljuthatna valamely kiszolgálóhoz, akkor a 0 0 számpárt kell kiírni. Több megoldás esetén bármelyik megadható.
Példa
| SZOLGA.BE | SZOLGA.KI |
11 3
1 3 5
4 0
11 0
4 6 5 0
1 3 6 8 0
7 3 6 0
4 3 5 7 10 8 0
5 6 10 0
4 6 9 0
8 10 0
9 6 7 0
2 0
|
3
0 1
0 0
0 3
1 1
0 5
1 3
1 5
2 4
3 8
2 6
0 0
|
Tesztadatok
Nincs.
