Straus ehtirasları
Conni ilə dəvəquşu Çak arasında baş verən xoşagəlməz hadisədən sonra, fermer gələcəkdə belə bir qarışıqlığın qarşısını almaq üçün tədbirlər görməyə qərar verdi.
Conni quşlar üçün yeni bir yaşayış sahəsi qurmaq istəyir. O, N müşahidə qülləsi tikərək, onları elektrikli tikanlı məftillərlə birləşdirib, dəvəquşuların yaşayacağı N zirvəli çoxbucaqlı bir həyət yaratdı. Müşahidəni asanlaşdırmaq üçün, bəzi qonşu olmayan qüllə cütlərini divarlarla birləşdirərək həyəti N-2 üçbucaq hissəyə bölmək istəyir. Bu, dəvəquşular üçün qəfəslər təşkil edəcək. Təbii ki, divarlar tamamilə çoxbucaqlı daxilində olmalıdır və hər bir qəfəs qeyri-degenerativ üçbucaq təşkil etməlidir, yəni sahəsi sıfır olmamalıdır.
İndi fermer həyəti necə böləcəyini seçməlidir. Ona divarların çəkilməsi üçün bütün mümkün variantları təhlil etməkdə kömək edin. Conni iki sualla maraqlanır - biri daha sadə, digəri isə daha çətin. Birincisi, hansı qüllə cütləri arasında divar olan bir bölmə planı mövcuddur. İkincisi, ümumiyyətlə həyəti bölmək üçün neçə plan mövcuddur.
Giriş verilənləri
Giriş faylının ilk sətirində N (3 ≤ N ≤ 300) - qüllələrin sayı verilir.
Sonrakı N sətirdə qüllələrin təsvirləri onların keçid sırasına görə verilir. i-ci sətir x_i, y_i modulu 10^4-dən çox olmayan iki tam ədədi ehtiva edir - i-ci qüllənin koordinatları.
Həyətin öz-özünə toxunmayan və kəsişməyən qeyri-sıfır sahəli çoxbucaqlı olduğu təmin edilir.
Çıxış verilənləri
Birinci sətirdə potensial olaraq aralarında divar çəkilə bilən qüllə cütlərinin sayı K verilməlidir.
Sonra hər sətirdə bir cüt qüllə nömrəsi olmaqla K cüt nömrə verin. Hər cütdəki ədədlər artan qaydada olmalıdır, cütlər əvvəlcə birinci ədədlərin artan qaydasına, sonra isə ikinci ədədlərin artan qaydasına görə sıralanmalıdır.
Sonuncu sətir yalnız həyəti qəfəslərə bölmək yollarının sayını ehtiva etməlidir. Çünki bu kifayət qədər böyük ola bilər, onun 2^30 = 1073741824 ilə bölünməsindən qalanı verin.