Напомена: ово је незванична копија задатака. Као таква, не гарантује се да ће овај сајт бити одржаван, и немојте се изненадити ако са њега задаци одједном нестану.
Мали Мика се налази на Северном полу и стоји на једној од
многобројних санти леда. Он жели да дође до свог пријатеља Лазе који се
налази на другој санти. Између неких парова санти се налази вода која је
или у потпуности течна, или пуна малих комада леда (тешко је проћи кроз
њу). Мика има машину која уништава мале комаде леда (само њих, не и
санте), и она је на почетку угашена, а он може да је
пали и гаси произвољан број пута.
Све док је машина упаљена, он
може прећи пут између две санте који има комадиће леда (који се након
његовог проласка мистериозно врате), а не сме да прелази пут који нема
(јер би се машина покварила), те је мора угасити за овакав пут (и не
треба да је пали док не дође поново до неког пута са ледом).
Потребно је наћи начин да Мика дође до Лазе тако да најмањи број
пута мења стање своје машине (напомена: машина може бити у
било ком стању када Мика дође до Лазине санте).
У првој линији дати су број санти \(N\), број путева између санти \(M\) (ако не постоји пут између неке две
санте сматрамо да је превише непроходан и да Мика не може директно доћи
од једне до друге).
Затим је дато \(M\) линија где су \(a\), \(b\), и \(t\) раздвојени размаком, ови бројеви значе
да постоји пут између \(a\)-те санте и
\(b\)-те санте, док број \(t\) представља тип пута - \(1\) ако је пун леда, а \(0\) ако није.
На крају се учитавају
два броја \(u,v\) која представљају
редни број санте где се налазе Мика и Лаза (редом).
На стандардном излазу исписати један број - најмањи могући број
промена стања машине. Уколико не постоји начин да Мика дође до
Лазе, исписати -1.
4 4
1 2 1
1 3 1
2 3 0
3 4 0
1 42Можемо отићи у санту 2 или 3 (што свакако захтева паљење машине), а касније или из 2 у 3 и даље у 4 (што захтева 1 гашење), или из 3 у 4 (што такође захтева гашење), и да тако променимо стање два пута.
7 6
1 2 0
1 3 1
2 4 1
3 5 0
5 6 1
6 7 0
1 74Једино смер посећивања \(1-3-5-6-7\) нас доводи до санте број 7.