یک گراف n راسی داریم که به هر یال آن یک رنگ نسبت دادهایم. حال میخواهیم یک مسیر از راس s به راس t پیدا کنیم کمترین مقدار تغییر رنگ را داشته باشد.
مقدار تغییر رنگ در مسیر s=k0,k1,k2,...,k3=t برابر است با تعداد 0<j<r هایی که رنگ یال (kj−1,kj) و یال (kj,kj+1) متفاوت باشد.
در خط اول فایل ورودی به ترتیب اعداد n و s و t آمدهاند. سپس نیمهی پایین ماتریس مجاورت گراف آمده است. میدانیم n≤100 و تعداد یالهای گراف کمتر یا مساوی ۱۰۰۰ است. اعداد ماتریس تماما نامنفی هستند و نشاندهندهی رنگ یالهای گراف میباشند. (عدد ۰ یعنی یالی وجود ندارد)
در فایل خروجی مقدار تغییر رنگ مسیر مورد نظر را بنویسید.