Kiber-hücum

Vi, Arasaka korporasiyasının serverlərini sındırmağa çalışır ki, mühafizəni söndürüb onların ofisinə daxil olsun. Serverin süni intellekti isə buna mane olmağa çalışır.

Sındırma prosesi aşağıdakı kimi baş verir. Hər bir kənarında ingilis əlifbasının hərfi yazılmış istiqamətli qrafı nəzərdən keçirək. Qraf çoxlu kənarlar və hətta döngələr də ehtiva edə bilər. Vi-nin bir tokeni var və əvvəlcə müəyyən bir zirvədə v yerləşir. Serverin süni intellektinin də bir tokeni var və əvvəlcə müəyyən bir zirvədə u yerləşir. Onlar növbə ilə hərəkət edirlər, Vi birinci hərəkət edir. Öz növbəsində Vi, tokeninin yerləşdiyi zirvədən çıxan istənilən kənarı seçir. O, tokeni bu kənar boyunca hərəkət etdirir və həmçinin c tipli hücum etməyə çalışır, burada c seçilmiş kənarda yazılmış simvoldur. Süni intellekt öz növbəsində tokeninin yerləşdiyi zirvədən çıxan kənarlardan birini seçir və tokeni bu kənar boyunca hərəkət etdirir. Bununla belə, hücumu uğurla dəf etmək üçün o, üzərində eyni c simvolu yazılmış kənarı seçməlidir.

Əgər Vi hərəkət edə bilmirsə, çünki tokeninin yerləşdiyi zirvədən heç bir kənar çıxmırsa, sındırma uğursuzluqla başa çatır. Əgər süni intellekt tokeninin yerləşdiyi zirvədən çıxan və üzərində c simvolu yazılmış kənarı seçə bilmirsə, sındırma uğurla başa çatır. Həmçinin, Vi və süni intellektin sonsuz müddət ərzində hərəkət etməsi mümkün olan bir vəziyyət də mümkündür.

Vi-yə optimal hərəkətlər zamanı sındırmanın uğurla həyata keçiriləcəyi başlanğıc vəziyyətlərinin, yəni zirvə cütlərinin v və u sayını müəyyən etməyə kömək edin.

Giriş məlumatları

Birinci sətirdə qrafın zirvələrinin və kənarlarının sayı olan iki tam ədəd n və m (1 ≤ n ≤ 1000, 0 ≤ m ≤ 1000) verilir.

Növbəti m sətirdə qrafın kənarlarının təsviri verilir. Hər bir sətir iki tam ədəd a[i] və b[i] və ingilis əlifbasının kiçik hərfi c[i] ehtiva edir, onlar a[i] zirvəsindən b[i] zirvəsinə olan və üzərində c[i] simvolu yazılmış kənarı göstərir (1 ≤ a[i], b[i] ≤ n).

Çıxış məlumatları

Bir ədəd çıxarın - axtarılan başlanğıc vəziyyətlərinin sayı.

Qeyd

Birinci nümunədə, əgər Vi və süni intellektin tokenləri eyni zirvədədirsə, proses heç vaxt başa çatmayacaq. Bütün digər hallarda, sındırma uğurlu olacaq.