Qapıların tikintisi
Con fermasında hasar çəkir.
Con başlanğıcda (0, 0) mövqeyindədir və hər dəfə şimal, cənub, şərq və ya qərb istiqamətində bir addım ataraq n addım atır. Hər addım atdıqda, arxasında hasar çəkir. Məsələn, əgər ilk addımı şimala olsa, (0, 0) nöqtəsindən (0, 1) nöqtəsinə qədər hasar seqmenti əlavə edəcək. Con eyni nöqtələri dəfələrlə ziyarət edə bilər və hətta eyni hasar seqmentlərini dəfələrlə çəkə bilər. Onun hasarı hətta özünü dəfələrlə kəsə bilər.
Nəticədə, Con hasarlarla fermasını bir neçə müstəqil hasarlanmış sahəyə bölə bilər. O, bu vəziyyəti düzəltmək üçün qapılar əlavə etmək istəyir. Qapı, bu seqmentin iki tərəfi arasında keçidi təmin etmək üçün vahid uzunluqlu hər hansı bir seqmentə quraşdırıla bilər.
Hər bir bölgənin digər bölgələrdən əlçatan olmasını təmin etmək üçün tələb olunan minimum qapı sayını müəyyən edin.
Giriş məlumatları
Birinci sətir n (1 ≤ n ≤ 1000) ədədini ehtiva edir. Növbəti sətir Con-un yolunu təsvir edən uzunluğu n olan bir sətirdir. Hər bir simvol N (şimal), E (şərq), S (cənub), W (qərb) simvollarından biridir.
Çıxış məlumatları
Con-un fermasının bütün bölgələrinin tam əlaqəsini bərpa etmək üçün qurmalı olduğu minimum qapı sayını çıxarın. Qeyd edək ki, əgər ferma əvvəlcədən əlaqəlidirsə, cavab 0 ola bilər.