یک گراف $n$ راسی داریم که به هر یال آن یک رنگ نسبت داده‌ایم. حال می‌خواهیم یک مسیر از راس $s$ به راس $t$ پیدا کنیم کم‌ترین مقدار تغییر رنگ را داشته باشد.

مقدار تغییر رنگ در مسیر $s=k_0,k_1,k_2,...,k_3=t$ برابر است با تعداد $0<j<r$ هایی که رنگ یال $(k_{j-1},k_j)$ و یال $(k_j,k_{j+1})$ متفاوت باشد.

در خط اول فایل ورودی به ترتیب اعداد $n$ و $s$ و $t$ آمده‌اند. سپس نیمه‌ی پایین ماتریس مجاورت گراف آمده است. می‌دانیم $n\leq 100$ و تعداد یال‌های گراف کم‌تر یا مساوی ۱۰۰۰ است. اعداد ماتریس تماما نامنفی هستند و نشان‌دهنده‌ی رنگ یال‌های گراف می‌باشند. (عدد ۰ یعنی یالی وجود ندارد)

در فایل خروجی مقدار تغییر رنگ مسیر مورد نظر را بنویسید.

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