Fişierul intrare/ieşire:revolta.in, revolta.outSursăACM ICPC - Romanian Programming Contest 2016
AutorStefan RusetiAdăugată destefanrStefan Ruseti stefanr
Timp execuţie pe test2 secLimită de memorie66432 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Revolta

Marele Imperiu Galactic cuprinde mai multe sisteme solare locuite. Bineînţeles, distanţele între sisteme sunt uriaşe, aşa că pentru deplasarea dintre ele au fost generate găuri de vierme între diverse perechi de planete. Găurile de vierme sunt bidirecţionale, însă necesită extrem de multă energie pentru a le păstra deschise. În cadrul imperiului, se poate circula între oricare două sisteme, însă Împăratul a decis să nu existe mai multe de un mod de a ajunge între două sisteme, pentru a menţine costurile la minim.

Locuitorii din colţurile îndepărtate ale galaxiei s-au revoltat pentru că au de făcut prea multe salturi pentru a ajunge în anumite sisteme. Pentru a calma populaţia, Împăratul a decis să mai genereze o gaură de vierme, dezactivând însă una existentă. Pentru a mulţumi pe toată lumea, gaura de vierme construită şi cea distrusă vor fi alese pentru a minimiza numărul maxim de salturi între oricare două sisteme din galaxie.

Date de intrare

Fişierul de intrare revolta.in va conţine pe prima linie un singur număr, t, reprezentând numărul de teste. Fiecare test va începe cu numărul de sisteme din galaxie, n, urmat de n-1 linii de forma a b, reprezentând câte o gaura de vierme între sistemele a şi b.

Date de ieşire

În fişierul de ieşire revolta.out se va afişa, fiecare test, o linie conţinând numărul minim de salturi care se poate obţine după înlocuire. Dacă numărul iniţial de salturi era deja optim, se va afişa acesta.

Restricţii

  • 1 ≤ t ≤ 10
  • 2 ≤ n ≤ 100000
  • 0 ≤ a, b < n

Exemplu

revolta.inrevolta.out
2
4
0 1
1 2
2 3
4
0 1
1 2
1 3
2
2
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?