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