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