Masala #0593
Plus-Minus
Plus va minus bir birini yoqtirmaydi. Ular joylashgan qishloqda \(N\) ta(\(1\) dan \(N\) gacha raqamlangan) chorraha va bu chorrahalarni bog'lab turuvchi \(M\) ta bir xil uzunlikdagi ikki tomonlama harakat qiladigan yo'llar mavjud. Plus minus turgan chorrahaga, minus esa plus turgan chorrahaga borishni istaydi ammo ikkisi bir chorrahada uchrashib qolishni istamaydi (umumiy yo'lda qarama qarshi harakatlanishi mumkin 1-testga qarang). Ikkisi ham optimal harakat qilib plus \(N-\)chorrahaga, minus \(1-\)chorrahaga borishi kerak. Ularning tezliklari bir xil va doim harakatda qachonki ikkisi ham manziliga bir vaqtda yetib kelsa harakatni to'xtatadi. Dastlab plus \(1-\)chorrahada, minus esa \(N-\)chorrahada joylashgan.
Kirish faylining dastlabki satrda \(N(2\leq N\leq200)\) va \(M(1\leq M\leq N(N-1)/2)\) ikkita natural son mos ravishda chorrahalar va yo'llar soni. Keyingi \(M\) ta satrda \(u, v(1\leq u,v\leq N)\) \((u\neq v)\) chorrahalar o'rtasida yo'l mavjudligi.
Chiqish faylining birinchi satrda plus va minus ikkisi ham bir xil vaqtda manziliga yetib olguncha minimal tashrif buyurgan chorrahalar soni \(K\) va keyingi 2 ta satrda mos ravishda "P:" va "M:" belgilari va K tadan son ketma-ket tashrif buyurish chorrahalarni probel bilan ajratilgan holda chop eting (agar bunday yechimlar bir nechta bo'lsa istalganini, dastlab plusni harakatini keyingi satrda minusni harakatini chop eting). Agar ikkisi bir vaqtda manzilga borishning imkoni bo'lmasa "Infinite!" so'zini ni chop eting.
| # | input.txt | output.txt |
|---|---|---|
| 1 |
2 1 1 2 |
2 P: 1 2 M: 2 1 |
| 2 |
5 4 1 2 4 3 3 1 5 3 |
Infinite! |
| 3 |
7 6 1 6 1 5 7 5 3 4 2 7 5 3 |
7 P: 1 5 3 4 3 5 7 M: 7 2 7 5 1 6 1 |
1-test: Plus va minus umumiy yo'lda qarama qarshi harakatda o'tib ketadi va ikkisixam bir vaqtda ma'nzilga yetib keladi.
2-test: Plus va minus hech qachon ma'nziliga yetib borishining imkoni bo'lmaydi.
3-test: Plus va minus ma'nziliga yetib borishi uchun harakati rasimda tasvirlangan(plus-yashil va minus-qizil rang bilan ifodalangan).
Telegram kanalimizga obuna bo'ling