İnək niyə yolu keçdi (Platin)

Fermer Ceyms $n$ növ inək yetişdirir və onun hər tarlası yalnız bir müəyyən növün inəklərini otarmaq üçün nəzərdə tutulub. Məsələn, $12$ növü üçün nəzərdə tutulmuş tarla yalnız $12$ növünə aid inəklər tərəfindən istifadə oluna bilər, digər növlərə aid inəklər tərəfindən yox.

Fermer Ceymsin fermasından uzun bir yol keçir. Yolun bir tərəfində $n$ tarladan ibarət ardıcıllıq yerləşir — hər növ üçün bir tarla, digər tərəfində isə yenə $n$ tarladan ibarət başqa bir ardıcıllıq var, orada da hər növ üçün bir tarla mövcuddur. İnək yolu keçdikdə, o öz növü üçün nəzərdə tutulmuş iki tarla arasında hərəkət edir.

Əgər Fermer Ceyms hər şeyi əvvəlcədən diqqətlə planlaşdırsaydı, tarlaları yolun hər iki tərəfində eyni qaydada düzərdi, belə ki, hər növ üçün olan iki tarla bir-birinin düz qarşısında olsun. Bu halda inəklər digər növlərin inəkləri ilə kəsişmədən yolu keçə bilərdilər. Təəssüf ki, yolun iki tərəfindəki tarlaların qaydası fərqli ola bilər, buna görə də bəzi növ cütləri kəsişən yollara malik ola bilər. Fərqli növlərdən ibarət $(a,b)$ cütü, əgər $a$ növü üçün yol boyunca mümkün olan istənilən keçid yolu $b$ növü üçün mümkün olan istənilən keçid yolu ilə mütləq kəsişirsə, «kəsişən cüt» adlanır.

Fermer Ceyms kəsişən növ cütlərinin sayını minimuma endirmək istəyir. Təşkilati səbəblərdən o, yolun bir tərəfindəki tarlaları «dövri sürüşdürmə» vasitəsilə yenidən düzə bilər. Yəni müəyyən 0 \le k < n üçün hər tarla $k$ mövqe irəli sürüşdürülür, bununla da son $k$ mövqedə olan tarlalar ilk $k$ mövqeyə keçir.

Məsələn, əgər yolun bir tərəfindəki tarlalar başlanğıcda növlərə görə 3, 7, 1, 2, 5, 4, 6 ardıcıllığı ilə düzülübsə və k = 2 üçün dövri sürüşdürmə yerinə yetirilirsə, yeni ardıcıllıq 4, 6, 3, 7, 1, 2, 5 olacaqdır.

Yolun tərəflərindən birindəki tarlaların uyğun dövri sürüşdürülməsindən sonra alına biləcək kəsişən növ cütlərinin minimum mümkün sayını təyin edin.