در کشور مانگالیا ‎$n$‎ شهر با شماره‌های ‎۱‎ تا ‎$n$‎ وجود دارد که بین هر دو شهر متوالی (با شماره‌ی ‎$i$‎ و ‎$i+1$‎) دقیقا دو جاده وجود دارد. هر یک از این ‎$2n-2$‎ جاده با یک رنگ خط‌کشی شده است. شنگول و منگول می‌خواهند از شهر ‎۱‎ به شهر ‎$n$‎ بروند، به این شرط که مجموعه‌ی رنگ‌هایی که هر یک از آن‌ها در جاده‌های مسیر خود می‌بیند اشتراک نداشته باشند. الگوریتمی از ‎$O(n)$‎ ارائه دهید که دو مسیر با شرایط گفته شده را بیابد، یا اعلام کند که این کار امکان پذیر نیست. درستی آن را اثبات نمایید.

• سوال بعد
• سوال قبل