+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- محمد گرافی شامل $n$ راس و $m$ یال دارد هر یال در گراف محمد یکی از $k$ رنگ موجود را دارد. پارسا برایش سوال پیش آمده است که اگر از راس $s$ در گراف شروع کند و به راس $t$ بخواهد برود حداقل چندبار باید رنگ یال هایی که می‌پیماید را عوض کند. # ورودی ورودی تنها شامل $m+2$ خط است که در خط اول آن سه عدد طبیعی $n$ و $m$ و $k$ با فاصله و به ترتیب از هم آمده است. $$1 \le n, m \le 100$$ $$1 \le k \le 10^3$$ در خط دوم دو عدد $s$ و $t$ به ترتیب آمده است. در $m$ خط بعد ۳ عدد $a_i$ و $b_i$ و $k_i$ آمده است که نشان دهنده وجود یال با رنگ $k_i$ بین $a_i$ و $b_i$ می‌باشد. # خروجی در خروجی تنها حداقل تعداد رنگ عوض کردن ها خروجی داده شود. اگر این کار امکان پذیر نبود `1-` چاپ شود. # مثال ## ورودی نمونه ۱ ``` 3 2 2 1 3 1 2 1 2 3 2 ``` ## خروجی نمونه ۱ ``` 1 ``` ## ورودی نمونه ۲ ``` 4 4 2 1 4 1 2 1 2 3 1 3 4 1 1 3 2 ``` ## خروجی نمونه ۲ ``` 0 ``` ## ورودی نمونه ۳ ``` 4 3 2 1 4 1 2 1 2 3 2 3 4 1 ``` ## خروجی نمونه ۳ ``` 2 ```