Dördhissəli qraflarda çoxluq
Dördhissəli qraflarda çoxluq
Təpəsi 4 qrupa bölünən və tili yalnız I və II, II və III, III və IV, IVvə I qruplarının təpələrini birləşdirən qraf verilmişdir. Sizə lazımdır ki, bu qrafda seçmək mümkün olan kəsişməyən 4-təpəli dövrlərin ən çox sayını tapasınız. Hər dövrdə hər bir qrupdan bir təpə yerləşməlidir və I və II, II və III, III və IV, IVvə I qruplarından olan təpələr tildə birləşməlidir.
Giriş verilənləri
Girişin birinci sətrində testlərin T (1 ≤ T ≤10) sayı yerləşir. Sonrakı T sayda testin hər birində I, II, III və IV qruplarındakı təpələrin sayı olan 4 ədəd- N1, N2, N3, N4 (1 ≤ N1, N2, N4 ≤10, 1 ≤ N3 ≤ 7) ədədləri yerləşir.
Daha sonra N1 sayda sətir gəlir. (2i+1)-ci sətirdə (0 ≤ i ≤ N1–1) I qrupun i-ci təpəsi ilə qonşu olan II qrupun təpələrinin sayı, sonra isə bu təpənin nömrəsi yerləşir. (2i+2)-ci sətirdə I qrupun i-ci təpəsi ilə qonşu olan IV qrupun təpələrinin sayı, sonra isə bu təpənin nömrəsi yerləşir(Hər bir qrupda təpələr 0-dan başlayaraq nömrələnmişdir).
Onların ardınca 2N3 sayda sətir gəlir.(2i+1)-ci sətrdə (0 ≤ i ≤ N3–1) I qrupun i-ci təpəsi ilə qonşu olan II qrupun təpələrinin sayı, sonra isə bu təpənin nömrəsi yerləşir. (2i+2)-ci sətirdə III qrupun i-ci təpəsi ilə qonşu olan IV qrupun təpələrinin sayı, sonra isə bu təpənin nömrəsi yerləşir.
Çıxış verilənləri:
T sayda sətrin hər birini "Case #A: B" şəklində verin. Burada A testin nömrəsi(1-dən başlayaraq), B verilmiş test üçün axtarılan kəmiyyətdir.
2 1 3 2 4 3 0 1 2 4 0 1 2 3 2 0 1 1 0 2 1 2 2 1 3 4 7 4 7 3 0 1 5 3 0 1 5 3 0 2 6 3 0 2 6 3 1 2 6 3 1 2 6 3 0 1 2 3 0 1 2 2 0 2 2 0 2 1 0 1 0 2 1 0 2 1 0 2 0 1 2 0 1
Case #1: 1 Case #2: 3