Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

JBART - Bajtocja

Za górami, za lasami, za rzekami, za morzami jest kraj potężny i bogaty zwany Bajtocją. Panuje tam dobrotliwy król Bajtazar I Wielki, słynny ze swej troski o infrastrukturę kraju. W Bajtocji jest n miast. Władca rozkazał swoim m nadwornym architektom przygotować projekty nowych ponaddźwiękowych traktów konnych. Jako odpowiedź dostał m propozycji, każda z nich składa się z trzech liczb p, k, w, gdzie p i k są miastami końcowymi traktu (trakt łączy te miasta bezpośrednio i nie przechodzi przez inne miasta), a w jest kosztem zbudowania tego traktu. Każdy trakt jest dwukierunkowy. Zamierzeniem króla jest budowa sieci traktów tak, aby można było nimi przejechać między każdymi dwoma miastami, być może odwiedzając po drodze inne miejscowości. Bajtazar jest bardzo oszczędnym królem, więc postanowił zgodzić się tylko na taką sieć, która jest możliwie najtańsza.

Napisz program BAJ, który:
- wczyta liczbę miast, liczbę proponowanych traktów oraz opisy tych traktów ze standardowego wejścia,
- dla każdego traktu określi, czy istnieje taka sieć połączeń między miastami, zgodna z królewskimi rozkazami i w której rozpatrywany trakt, wybudowany za wskazaną kwotę, jest wykorzystywany,
- wypisze na standardowe wyjście zestawienie uzyskanych wyników.

Input

Pierwszy wiersz wejścia zawiera dwie liczby całkowite: n - liczbę miast i m - liczbę proponowanych traktów, rozdzielone jedną spacją i spełniające warunki 2<=n<=7000, 1<=m<=300000. Każdy z kolejnych m wierszy zawiera po trzy liczby całkowite p, k, w rozdzielone pojedynczymi spacjami, opisujące proponowany trakt, przy czym p i k oznaczają miasta będące końcami traktu, zaś w jest ceną budowy tego traktu (1 <= p, k <= n, 1 <= w <= 100000).

Output

W każdym z kolejnych m wierszy należy wypisać jedno ze słów TAK albo NIE, w zależności od tego, czy istnieje plan budowy zgodny z życzeniami króla, czyli taki, że trakt opisany w odpowiednim wierszu jest w nim zawarty, czy też nie

Uwaga: w swoim rozwiązaniu możesz założyć, że istnieje plan budowy zgodny z zaleceniami króla.

Example

Input:
6 10
1 2 2
1 6 1
1 5 3
4 1 5
2 6 2
2 3 5
4 3 4
3 5 4
4 5 4
5 6 3

Output:
TAK
TAK
TAK
NIE
TAK
NIE
TAK
TAK
TAK
TAK

Zadanie pochodzi z Olimpiady Informatycznej dla Gimnazjum z roku szkolnego 2006/2007 z I etapu.


Dodane przez:Jarosław Drzeżdżon
Data dodania:2007-01-19
Limit czasu wykonania programu:1s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: GOSU
Pochodzenie:http://www.oi.edu.pl/oig

ukryj komentarze
2013-04-19 20:51:24 Piotr KÄ…kol
@Wiktor - Tutaj wytłumaczyłem, na czym polega zadanie.
2013-04-19 15:54:33 Wiktor
nie bardzo rozumiem. Zostały odrzucone 2 trakty. Żeby połączyć wszystkie miejscowości ze sobą można odrzucić też trakt miedzy 2-6 (lub 1-5), 5-6 oraz 4-5, ponieważ już są połączenia miedzy tymi miastami poprzez inne miejscowości, a to obniży koszt sieci o 9.
Czy dobrze rozumuje, jeśli nie to prosze o komentarz.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.