Улаанбаатар хотын автобусны сүлжээг дараах байдлаар загварчилъя.

Хотод нийт N буудал байна. Зарим буудлууд хоорондоо шууд автобусны замаар холбогдсон байдаг.

• Буудал бүрийг нэг орой (node)
• Хоёр буудлын хооронд шууд зам байвал ирмэг (edge)

гэж үзье.

Та нэг буудлаас эхэлж автобусанд суун, ихдээ K удаа дамжин (өөр буудлаар дамжин) бусад буудлууд руу очиж болно. Бүх автобус 2 буудалын хооронд л явах боломжтой байдаг.

? Зорилго

? Ямар буудлаас эхэлбэл:

• хамгийн олон өөр буудал руу
• K алхмын дотор (≤ K зам дамжин) хүрч болох вэ?

Оролт:

Эхний мөрөнд гурван бүхэл тоо өгөгдөнө:

N M K

• N — буудлын тоо
• M — замын тоо
• K — хамгийн их дамжлагын тоо

Дараагийн M мөр бүрт хоёр бүхэл тоо өгөгдөнө:

u v

• u болон v буудлын хооронд шууд зам байна

? Энэ нь чиглэлгүй (undirected) граф

Гаралт:

Нэг мөрөнд хоёр бүхэл тоо хэвлэнэ:

X Y

• X — хамгийн олон хүрч болох буудлын тоо
• Y — тийм боломжтой буудлын хамгийн бага дугаар

? Хэрэв хэд хэдэн буудал ижил тооны буудалд хүрч чадвал, хамгийн бага индексийг хэвлэнэ.

Хязгаарлалтууд:

• 1 ≤ N ≤ 100000
• 0 ≤ M ≤ 100000
• 0 ≤ K ≤ N
• 1 ≤ u, v ≤ N

Дэд бодлого

Жишээ:

Оролт-1

5 4 1
1 2
2 3
3 4
4 5

Гаралт-1

2 2

Тайлбар

K = 1 тул зөвхөн шууд хөршүүдийг тоолно.

• 1 → {2} → 1
• 2 → {1,3} → 2
• 3 → {2,4} → 2
• 4 → {3,5} → 2
• 5 → {4} → 1

? хамгийн их = 2
? хамгийн бага индекс = 2

Оролт-2

5 4 2
1 2
2 3
3 4
4 5

Гаралт-2

4 3

Тайлбар

K = 2:

• 3-аас: → {1,2,4,5} → 4 буудал

? хамгийн их = 4
? node = 3

Оролт-3

4 0 2

Гаралт-3

0 1

Тайлбар

Ямар ч зам байхгүй → хэн ч хаашаа ч хүрэхгүй

? бүх node → 0
? хамгийн бага индекс = 1