گراف $G$ که رئوس آن با $k$ رنگ، رنگ‌آمیزی شده‌اند به ما داده شده است (دقت کنید که ممکن است رنگ‌آمیزی خوب نباشد، یعنی دو راس مجاور رنگ یکسانی داشته باشند). حال دو راس $s$ و $t$ را به ما می‌دهند و از ما می‌خواهند که مسیری از $s$ به $t$ که از هر رنگ دقیقا یکی داشته باشد را در زمان در خروجی بدهیم (دقت کنید که ممکن است چنین مسیری وجود نداشته باشد و در خروجی Impossible را بدهیم). الگوریتمی در زمان $O(2^k\times f(n))$ که در آن $f(n)$ یک چند جمله‌ای بر حسب $n$ می‌باشد، برای این کار ارائه دهید.

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