Напомена: ово је незванична копија задатака. Као таква, не гарантује се да ће овај сајт бити одржаван, и немојте се изненадити ако са њега задаци одједном нестану.
Сунце поново сија, Београд је озеленео и расцветао се, топли дани су се вратили и као што се може претпоставити чланови комисије изненада више немају времена за СИО. Међутим, да би олакшали себи посао тајно су запослили једног младог члана да направи задатке за њих. Оно што нису знали јесте да је он сковао подмукли план са циљем да упропасти СИО и преузме посао комисије. Назваћемо нашег зликовца Никола.
Никола је инсталирао вирус на \(N\) рачунара намењених такмичарима. Сасвим случајно се десило да је тих \(N\) рачунара повезано помоћу \(N-1\) каблова (један кабал спаја два рачунара) тако да рачунари формирају стабло.
Комисија је морала да се поново активира и санира новонастали проблем. ‘Антивирус’, који су направили у те сврхе, функционише тако што комисија бира два рачунара \(а\) и \(b\), а затим покреће свој програм који са сваког рачунара на путу од \(а\) до \(b\), укључујући и њих, брише вирус ако постоји.
Помозите комисији да спаси све заражене рачунаре и то помоћу минималног броја покретања антивируса тако што ћете одредити тај број и навести им парове рачунара за које треба да позову програм.
У првом реду стандардног улаза налази се један природни број \(N\) - број рачунара заражених вирусом. У наредних \(N-1\) редова налазе се по два природна броја \(a\) и \(b\) која означавају да су рачунари \(a\) и \(b\) повезани.
Опис излазних података.
5
1 3
1 4
2 3
3 52
1 4
2 5Постоје \(3\) подзадатка у којима додатно важи:
Може да постоји више начина на које се могу повезати рачунари како би се добило оптимално решење. Потребно је исписати само један, произвољан начин као решење задатка.