razboi

Razboiul lumilor

== include(page="template/taskheader" task_id="razboi") ==

==Include(page="template/taskheader" task_id="razboi")==

Poveste ...

Tara A are N orase numerotate de la 1 la N. Aceste orase sunt conectate prin strazi bidirectionale in asa fel incat exista exact un singur drum intre orice pereche de orase. Deoarece tara A a fost atacata de tara B, tara A vrea sa pozitioneze intr-unul din orasele ei comandamentul armatei. Din motive defensive, comandamentul trebuie plasat in orasul cu proprietatea ca maximul distantei dintre orasul ales si oricare alt oras este minima (in cazul in care un oras oarecare este atacat, comandamentul trebuie sa ajunga acolo cat mai repede posibil; folosind proprietatea de mai sus se incearca minimizarea pagubelor in cazul cel mai defavorabil).

h2. Cerinta

...

Gasiti toate orasele in care poate fi plasat comandamentul.

h2. Restrictii
...
h2. Date de intrare

Data de intrare
 
Fisierul de intrare razboi.in contine pe prima linie numarul T de teste. Urmatoarele linii descriu cele T teste. Prima linie a fiecarui test contine numarul N, reprezentand numarul de orase din tara A. Urmatoarele N-1 linii contin descrierea unei strazi - trei numere intregi separate prin spatii: A, B, D. A si B reprezinta numarul oraselor conectate de acea strada iar D reprezinta lungimea strazii.
 
h2. Date de Iesire
 
Pentru fiecare test afisati in fisierul razboi.out urmatoarea linie: "Testul nr #XXX", unde XXX reprezinta numarul testului respectiv. Afisati apoi pe urmatoarele linii numarul oraselor in care ar putea fi plasat comandamentul. Aceste numere trebuie afisate in ordine crescatoare.
 
h2. Restrictii

...

o 1 <= N <= 16000

h2. Date de iesire

o 1 <= D <= 10000

...

o 1 <= T <= 20

h2. Exemplu

| razboi.in | razboi.out |
| linia1
linia2
linia3
| linia1
linia2
|
== include(page="template/taskfooter" task_id="razboi") ==
 

|razboi.in |razboi.out |
 
|3 |Testul nr #1 |
| | |
|5 |4 |
| | |
|1 2 1 |Testul nr #2 |
| | |
|1 3 2 |1 |
| | |
|1 4 3 |2 |
| | |
|4 5 4 |Testul nr #3 |
| | |
|2 |2 |
| | |
|1 2 19 | |
| | |
|3 | |
| | |
|1 2 1 | |
| | |
|2 3 1 | |
 
 
 
==Include(page="template/taskfooter" task_id="razboi")==