Kənar Hal#4026
Qraf nəzəriyyəsində, bir qrafda uyğunluq və ya müstəqil kənar dəsti G = (V, E) uyğunluqdakı M, heç bir iki kənarın ortaq bir təpə paylaşmadığı kənar dəsti ME-dir.
Son zamanlarda xəbərlərdə oxudunuz ki, "Alfred Nobel xatirəsinə iqtisadi elmlər üzrə Sveriges Riksbank Mükafatı" (qeyri-rəsmi olaraq, İqtisadiyyat üzrə Nobel Mükafatı) 2012-ci ildə Alvin E. Roth və Lloyd S. Shapley-ə, iki tərəfli qrafda müəyyən meyarlara cavab verən uyğunluq tapmaq üçün alqoritmlərinə görə verildi. Siz də eşitmisiniz ki, dairəvi qraflarda uyğunluqların kimyada tətbiqləri var və düşüncələriniz daha əvvəlkindən daha lüks bir Milad alış-verişi ilə gözəl bir gələcək planı ətrafında cəmləşir!
Dairəvi qraf, C_n, n ≥ 3, təpə dəsti {1, ..., n} üzərində qurulmuş sadə istiqamətsiz qrafdır, kənar dəsti E(Cn) = {(a, b} | |a-b|≡1 mod n}. Bu qraf 2-müntəzəmdir və n kənar ehtiva edir. C_3, C_4, C_5 və C_6 qrafları Şəkil 1-də təsvir edilmişdir.
Şəkil 1: C_3, C_4, C_5 və C_6 qrafları.
Nobel Mükafatı şöhrətinə doğru ilk addımınız dairəvi qraf C_n-də uyğunluqların sayını hesablamaqdır. Şəkil 2-də C_4 qrafının yeddi uyğunluğu təsvir edilmişdir.
Şəkil 2: C_4-ün uyğunluqları. Müvafiq uyğunluğun bir hissəsi olan kənarlar yaşıl rəngdədir, uyğunluqdan kənarda qalan kənarlar isə kəsik-kəsik göstərilmişdir. M_1 = Ø, M_2 = {{2, 1}}, M_3 = {{3, 2}}, M_4 = {{4, 3}}, M_5 = {{1, 4}}, M_6 = {{2, 1},{4, 3}}, və M_7 = {{3, 2},{1, 4}}.
Hər bir test üçün, bir müsbət tam ədəd olan bir sətir alırsınız: n, burada 3 ≤ n ≤ 10000.
Hər bir test üçün, C_n-də uyğunluqların sayını ehtiva edən bir sətir.
Nümunə 1