Sərsəri Qarışqalar#6203
Qarışqaların müəyyən bir koloniyası yemək axtarışındadır. Təəssüf ki, koloniyanın ətrafında gizli təhlükələr var ki, bu da yemək axtarışını çətinləşdirir. Tələlər, maneələr və yırtıcılar pusquda dayanıb. Xoşbəxtlikdən, koloniyada bu iş üçün mükəmməl bir qarışqa var. Maks nə ağıllı, nə də səmərəli bir qarışqadır, amma onun kor bəxti var. Bütün gəzintilərində həmişə təhlükəsiz yerdə qalmağı bacarıb və (nəhayət) həmişə koloniyaya geri bildirmək üçün bir yemək mənbəyi tapır.
Problem ondadır ki, Maks nadir hallarda yemək mənbəyinə çatmaq üçün optimal (ən qısa) bir marşruta bənzəyən bir yol tutur. Lakin, Maks yemək mənbəyinə çatmaq üçün getdiyi (tez-tez dolanbac və dolaşıq) yolun dəqiq detallarını etibarlı şəkildə geri gətirə bilir. Sizin işiniz koloniyaya Maksın dolaşıq istiqamətlərində yerləşən optimal marşrutu tapmaqda kömək etməkdir ki, koloniyanın daha səmərəli yemək axtarışı mümkün olsun.
Girişdəki ilk tam ədəd, 1 ≤ n ≤ 100, Maksın geri bildirdiyi yemək yollarının sayını göstərir. Bu, boş bir sətir və sonra n yolun təsvirləri ilə davam edir. Hər yol təsviri bir tam ədəd, s (0≤ s ≤ 60), ilə başlayır ki, bu da yolda atılan addımların sayını göstərir. Növbəti s sətir istiqamət addımlarını böyük hərflərlə ifadə edir: N, E, S və W, müvafiq olaraq şimal, şərq, cənub və qərb istiqamətində atılan addımları göstərir. Hər addım Maksı bir vahid məsafə hərəkət etdirir. Maksın yolları həmişə koloniyadan başlayır və bir yemək mənbəyində bitir. Hər bir yol təsviri cütlüyü arasında boş bir sətir var.
Optimal yolu axtararkən, yalnız Maksın əvvəllər atdığı addımlar və ya eyni addımların tərsi götürülə bilər.
Verilən hər bir yol üçün optimal (ən qısa) yolda tapılan addımların sayını verin.
Nümunə 1