Galaxy Bağlantısı

İlk ACM ICPC-dən $1000$ ildən çox vaxt keçib. Qalaktikamızın bir neçə sivilizasiyası, Yer planetini də daxil olmaqla, Böyük Dairəyə birləşiblər, bu dairənin üzvləri elmi və mədəni informasiyanı bir-birilə bölüşürlər. Qalaktikadakı cazibə və qaranlıq enerji axınlarının paylanmasına görə bəzi planetlər arasında ikitərəfli rabitə kanalları mövcuddur. Bu kanallar vasitəsilə sivilizasiyalar bütün Böyük Dairə boyunca bilik mübadiləsi aparır.

İndi isə araşdırmaların sivilizasiyalar arasında paylanma vaxtıdır: hər bir planet $k$ əsas araşdırma sahəsindən birini seçməlidir (məsələn, Düzgün Kalkulus və ya Verilmiş Sətir Nəzəriyyəsi kimi).

$k$ seçimi təsadüfi deyil. Böyük Dairə ilk olaraq Başlanğıc Dairəsi ilə başladı — $k$ planetin kanallarla birləşərək çevrə qurduğu dairə. Sonralar yeni kanallar kəşf edildi və quruldu, yeni planetlər Böyük Dairəyə qoşuldu. Lakin rabitə kanallarının yüksək enerji tələbatına görə, Böyük Dairədəki hər bir planetin kanallarının sayı dəqiq $k$-dən az oldu.

Birbaşa kanalla birləşən iki planet eyni araşdırma sahəsini seçməməlidir: daha yaxşı olar ki, fərqli sahələr seçsinlər və tədqiqat nəticələrini paylaşsınlar.

Daha bir məhdudiyyət də var. Müəyyən aralıqlarla sivilizasiyalar yeni planetləri kəşf etmək üçün kosmik ekspedisiyalar göndərir və Böyük Dairədə qonşuları ziyarət edirlər. Ekspedisiyalar belə planlanır ki, kosmik gəmi bir planetdən digərinə yalnız bir rabitə kanalı vasitəsilə keçə bilsin. Bu, ekspedisiyalara hazırlıqda — yanacaqdoldurma məntəqələrinin qurulmasında, gəmilərin rabitə sistemlərinin optimallaşdırılmasında və s. — kömək edir.

Bəzi ekspedisiyalar, Araşdırma Auditləri, belə planlanıb ki, gəmi bir planetdən başlayır, sonra k - 1 sıçrayış edir və ümumilikdə $k$ planet (başlanğıc planet daxil) ziyarət olunur. Bu $k$ planet birlikdə bütün $k$ araşdırma sahəsini əhatə etməlidir: ekspedisiya araşdırmaların gedişatını yoxlayacaq.

Sənin vəzifən hər planet üçün bir araşdırma sahəsi seçməkdir, belə ki: - Birbaşa bir rabitə kanalı ilə birləşən iki planetin araşdırma sahələri eyni olmasın; - Böyük Dairənin istənilən planetindən Araşdırma Auditi ekspedisiyasına başlamaq mümkün olsun.