Canavar yolları

Vəhşi Cəngəllikdə, Seeonee canavar sürüsündən başqa, Azad İnsanların bir çox digər qəbilələri də var. Hər sürünün öz adət-ənənələri, başçısı və Şura Qayası var. Cəngəllik bərabər kvadratlara bölünüb, hər qəbiləyə ov üçün müəyyən kvadratlar ayrılıb. Bəzən bir sürünün canavarları başqa sürünün şurasına qonaq gedə bilərlər.

Başqa bir sürünün ərazisinə daxil olarkən qarşıdurmaların qarşısını almaq üçün, sürü başçılarından ibarət ağsaqqallar məclisi Şura Qayaları arasında təhlükəsiz yollar qurmağa qərar verdi. Onların qərarı aşağıdakı kimidir:

• Hər bir Şura Qayası bir kvadratın mərkəzində yerləşməlidir.

• Hər iki Şura Qayası arasında yalnız bir sadə yol olmalıdır, bu isə bir və ya bir neçə cığırdan ibarət olmalıdır.

• Cığır mümkün olan ən qısa olmalıdır və qonşu kvadratların mərkəzlərini kənarları üzrə birləşdirən hissələrdən ibarət olmalıdır.

• İki Şura Qayası arasında cığır qoymaq olar, əgər onların aralarındakı məsafə $k$-dan çox deyilsə.

• Əgər iki Şura Qayası arasında 10^6-dan çox ən qısa cığır varsa, fərz edilir ki, aralarında məhz 10^6 cığır var.

• Hər bir Şura Qayası cütü arasında məhz bir ədədi kəsişməyən yol olmalıdır və bu, qurulan cığırların istifadəsi ilə olmalıdır.

Şura Qayaları arasında cığırları neçə fərqli üsulla qura biləcəyinizi hesablayan proqram yazın.