Razboiul lumilor

razboi

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

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

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).

Poveste ...

h2. Cerinta

Gasiti toate orasele in care poate fi plasat comandamentul.
 
 
 
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
 
o 1 <= D <= 10000

...

o 1 <= T <= 20

h2. Date de intrare

h2. Exemplu

...
h2. Date de iesire

|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 | |

...
h2. Exemplu
| razboi.in | razboi.out |
| linia1
linia2
linia3
| linia1
linia2
|

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

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