Qraf#3162
Gəlin zirvəsi və qırağı olan istiqamətsiz qrafı nəzərdən keçirək. Bu qrafın zirvələrini neçə müxtəlif üsulla boyamaq olar, əgər boyamaq üçün müxtəlif rəng mövcuddursa? Hər boyamada bütün rənglərdən istifadə etmək mütləq deyil. İki boyama eyni sayılır, əgər qrafın qıraqlarını saxlayan zirvələrin yenidən nömrələnməsi mövcuddur və hər iki boyamada -ci zirvənin rəngi eynidirsə. Məsələn, şəkildəki boyamalar eyni sayılır (uyğun nömrələnmə: 1 \to 1, 2 \to 2, 3 \to 4, 4 \to 3).
Girişin birinci sətrində üç tam ədəd var: , , və (1 \leq N \leq 9, 1 \leq M \leq 100, 1 \leq K \leq 10). Növbəti sətrin hər birində ilə arasında iki tam ədəd verilir — qırağın uclarını göstərir. Qrafda paralel qıraqlar və döngələr ola bilər. Sətrdəki ədədlər boşluqla ayrılmışdır.
Çıxışda yeganə tam ədəd olmalıdır — müxtəlif boyamaların sayı.
Nümunə 1