Čuvena hakerska grupa je razvila novu vrstu virusa, tzv. skakače, fokusirane na računarske mreže.
Računarska mreža je skup servera (
) i direktnih veza
(
).
Svaka direktna veza povezuje dva različita servera, dozvoljavajući im da komuniciraju
u oba smera. Ako je server
zaražen virusom, tim virusom će se zaraziti
i svi serveri
gde je
skup servera koji su direktno povezani sa nekim susedom
servera
. Formalno,
.
Novoinficirani server
može da nastavi da zaražava servere na isti način.
Vi hoćete da zarazite sve servere u nekoj mreži, tako što ćete izabrati jedan server i njega zaraziti virusom. Potom bi taj virus nastavio da zaražava ostale servere na opisani način. Nažalost može se desiti da na ovakav način nije moguće zaraziti sve servere u početnoj mreži. Srećom, shvatili ste da možete da dodate direktne veze između nekih servera.
Koliko je najmanje veza potrebno dodati tako da bi bilo moguće zaraziti sve servere, tako što ćete izabrati jedan server i njega zaraziti virusom?
Opis ulaza
Prva linija sadrži brojeve i
, gde
i
. Sledećih
linija
sadrže dva broja
i
(
), koji predstavljaju direktnu
vezu između dva servera
i
. Postoji najviše jedna veza između bilo koja
dva servera i ne postoji server koji je povezan direktnom vezom sa samim sobom.
Opis izlaza
Potrebno je ispisati samo jedan broj - najmanji broj veza koje je neophodno dodati.
Primer ulaza 1
3 2
1 2
2 3
Primer izlaza 1
1
Primer ulaza 2
5 10
1 2
2 3
3 4
4 5
5 1
1 3
2 4
3 5
4 1
5 2
Primer izlaza 2
0
Primer ulaza 3
12 13
2 3
3 4
4 5
5 2
6 7
7 8
8 9
9 10
10 7
9 12
12 11
11 6
12 7
Primer izlaza 3
3
Objašnjenje primera
U prvom primeru postoje servera i
direktne veze
.
U ovoj mreži ne postoji način da zarazimo sve servere, ako bi zarazili
samo jedan server, npr. ukoliko zarazimo server
, onda će samo serveri
i
zaraženi i sl.
Možemo da dodamo jednu direktnu vezu -
da bi postigli naš cilj.
Kada to uradimo, ako zarazimo server
, svi serveri,
,
, i
će biti zaraženi.
(stoga, server
je zaražen).
(stoga, server
je zaražen).
Comments