İnək niyə yolu keçdi III (Gümüş)#10537
Ferma Consinin fermi n \times n ölçülü xanalardan ibarət kvadrat şəbəkədir. Bəzi qonşu xana cütləri (şimal-cənub və ya qərb-şərq istiqamətində yerləşənlər) yollarla ayrılıb, şəbəkənin bütün xarici perimetri boyunca isə hündür bir hasar çəkilib ki, inəklər fermanı tərk edə bilməsinlər. İnəklər qonşu xanalar arasında şimal, şərq, cənub və qərb istiqamətlərində sərbəst hərəkət edə bilirlər, lakin zərurət olmadıqca yolları keçməyi xoşlamırlar.
Ferma Consinin fermasında inək var, hər biri ayrıca bir xanada yerləşir. Əgər bir inəyin digərinə çatması üçün ən azı bir yolu keçmək lazımdırsa, belə inək cütü "uzaq" adlanır. Ferma Consiyə "uzaq" inək cütlərinin sayını hesablamaqda kömək edin.
Birinci sətirdə üç tam ədəd və r~(2 \le n \le 100, 1 \le k \le 100, k \le n^2) verilir. Sonrakı sətirdə qonşu xana cütlərini ayıran yollar təsvir olunur. Hər sətir r~c~r'~c' formasındadır ( aralığında tam ədədlər) və sətri, sütunu olan xana ilə ona qonşu olan r' sətri, c' sütunu olan xana arasında yol olduğunu bildirir. Son sətirdə isə inəyin yerləşdiyi xanalar göstərilir — hər inək üçün onun xanasının sətir və sütun nömrəsi verilir.
"Uzaq" olan inək cütlərinin sayını çap edin.
Nümunə 1