==Include(page="template/taskheader" task_id="catun")==
==Include(page="template/raw")==
catun
Intr-un regat feudal exista mai multe asezari omenesti, numerotate de la 1 la N, intre care sunt construite drumuri de diverse lungimi. Dintre aceste asezari, o parte sunt fortarete, iar restul sunt simple catune. Fiecare fortareata trebuie sa aprovizioneze trupele stationate in ea, deci are nevoie de feude. In calitate de mare sfetnic al monarhului, vi se cere sa indicati feudele aservite fiecarei fortarete, respectiv toate acele catune care se afla mai aproape de fortareata in discutie decat de oricare alta. Daca un catun este la distanta egala de doua fortarete, se va considera ca apartine fortaretei cu numarul de identificare minim.
h2. Cerinta
Sa se determine pentru fiecare catun carei fortarete apartine.
h2. Date de Intrare
In fisierul de intrare catun.in se vor afla numarele N, M, K, indicand, in aceasta ordine, numarul de asezari, numarul de drumuri si numarul de fortarete. Cea de a doua linie a fisierului va contine K numere naturale distincte indicand numerele de ordine ale fortaretelor. Pe urmatoarele M linii, pana la sfarsitul fisierului, se vor gasi triplete de forma (x y z), semnificand faptul ca exista un drum bidirectional intre asezarile x si y si are lungimea z, exprimata in unitatea de masura pentru lungimi a Evului Mediu.
h2. Date de Iesire
Fisierul de iesire catun.out va contine o singura linie pe care se afla N numere naturale, al i-lea numar fiind 0, daca asezarea a i-a este o fortareata sau este un catun de la care nu se poate ajunge la nici o fortareata din cele K, sau numarul fortaretei de care se leaga asezarea a i-a, in caz contrar.
h2. Restrictii si precizari
o 1 <= K <= N <= 36 000
o 1 <= M <= 72 000
o Intre oricare doua asezari exista maxim un drum
h2. Exemplu
catun.in catun.out
8 9 2 5 0 5 0 0 5 0 2
2 5
1 3 6
1 5 3
1 6 1
2 3 9
5 6 5
6 8 7
3 6 2
4 7 1000
==Include(page="template/taskheader" task_id="catun")==
Intr-un regat feudal exista mai multe asezari omenesti, numerotate de la $1$ la $N$, intre care sunt construite drumuri de diverse lungimi. Dintre aceste asezari, o parte sunt fortarete, iar restul sunt simple catune. Fiecare fortareata trebuie sa aprovizioneze trupele stationate in ea, deci are nevoie de feude. In calitate de mare sfetnic al monarhului, vi se cere sa indicati feudele aservite fiecarei fortarete, respectiv toate acele catune care se afla mai aproape de fortareata in discutie decat de oricare alta. Daca un catun este la distanta egala de doua fortarete, se va considera ca apartine fortaretei cu numarul de identificare minim.
h2. Cerinta
Sa se determine pentru fiecare catun carei fortarete apartine.
h2. Date de Intrare
In fisierul de intrare $catun.in$ se vor afla numarele $N, M, K$, indicand, in aceasta ordine, numarul de asezari, numarul de drumuri si numarul de fortarete. Cea de a doua linie a fisierului va contine $K$ numere naturale distincte indicand numerele de ordine ale fortaretelor. Pe urmatoarele $M$ linii, pana la sfarsitul fisierului, se vor gasi triplete de forma $(x y z)$, semnificand faptul ca exista un drum bidirectional intre asezarile $x$ si $y$ de lungime $z$, exprimata in unitatea de masura pentru lungimi a Evului Mediu.
h2. Date de Iesire
Fisierul de iesire $catun.out$ va contine o singura linie pe care se afla $N$ numere naturale, al $i$-lea numar fiind $0$, daca asezarea a $i$-a este o fortareata sau este un catun de la care nu se poate ajunge la nici o fortareata din cele $K$, sau numarul fortaretei de care se leaga asezarea a $i$-a, in caz contrar.
h2. Restrictii si precizari
* $1 ≤ K ≤ N ≤ 36 000$
* $1 ≤ M ≤ 72 000$
* Intre oricare doua asezari exista maxim un drum
h2. Exemplu
table(example). |_. catun.in |_. catun.out |
| 8 9 2
2 5
1 3 6
1 5 3
1 6 1
2 3 9
5 6 5
6 8 7
3 6 2
4 7 1000
2 8 5
| 5 0 5 0 0 5 0 2 |
==Include(page="template/taskfooter" task_id="catun")==
2 8 5
==Include(page="template/taskfooter" task_id="catun")==
