Egy kommunikációs hálózat eszközökből és az őket összekötő kétirányú vezetékekből áll. Az eszközök egyikét a hálózat középpontjának jelöljük ki. A középpontnak bármely eszköztől indulva elérhetőnek kell lennie egy vagy több kommunikációs vonal felhasználásával. A megvalósított hálózat nem garantálja a középpont elérését.
Feladat:
Írj programot, amely minimális számú új kommunikációs vonal létrehozásával elérhetővé teszi a középpont elérését bármely más eszközből. Emellett a program adja meg az új kapcsolatok végpontjait!
Bemenet:
A bemeneti állomány néhány tesztesetet tartalmaz, amelyek hálózatot írnak le. Minden teszteset első sora három egészet, az N K és M értékét tartalmazza. Az N (1<=N<=1000) a hálózati eszközök számát adja meg, a K (1<=K<=N) a kijelölt középpont sorszáma és az M (1<=M<=5000) a kommunikációs kapcsolatok számát adja meg. Az ezt követő M sor mindegyikében egy-egy a, b számpár áll, ahol (1<=a, b<=N) egy kommunikációs kapcsolat két végpontja. A 0 0 0 sor zárja a bemeneti állományt.
Kimenet:
A kimenet tesztesetenként két sort tartalmaz. Az első sor egyetlen U egész számot tartalmaz, amely a szükséges kommunikációs vonalak számát adja meg. A következő sor U számpárt tartalmaz, amelyet az a, b egészek alkotnak, egy-egy kommunikációs csatorna végpontjait adják meg. Ha az U értéke 0, akkor a következő sornak üresnek kell lennie.
Példa:
|
centre.in |
centre.out |
|
3 1 3 |
0 2
7
1 8 1 |
(ACM SZTE csapatverseny 1999)