====== هپید ====== از آنجا که هپید دوباره شروع کرده بود به گریه کردن، افشین او را روی یکی از رأس‌های یک گراف جهت دار ‎$n$‎ رأسی گذاشت (رأس ‎$s$‎) و بهش گفت که توی رأس ‎$t$‎ از این گراف، یک مهدکودک جدید ساخته‌اند. هپید هم تصمیم گرفت که مسافرت خود را از ‎$s$‎ به ‎$t$‎ شروع کند. او با خود قرار گذاشت که در روز ‎$i$‎ام از مسافرتش ‎($i \ge 1$)‎، دقیقاً ‎$2^{i-1}$‎ یال از گراف را طی کند و اگر پس از طی این ‎$2^{i-1}$‎ جاده، در مهدکودک قرار نداشت، صبر کند تا روز بعد. البته این را در نظر داشته باشید که هپید تا ‎$k$‎ روز بعد از لحظه‌ی شروع مسافرتش عمر می‌کند. برنامه‌ای بنویسید که با دریافت گراف جهت‌دار و ساده‎ (در یک گراف ساده، از هیچ رأس به خودش یال نیست و از رأس ‎$i$‎ به رأس ‎$j$‎ بیش از یک یال وجود ندارد)، دو راس ‎$s$‎ و ‎$t$‎ از گراف، و عدد ‎$k$‎، اولین روزی که هپید می‌تواند قبل از پایان عمرش به مهدکودک برسد را در صورت وجود چاپ کند. ===== ورودی ===== * ‎‎در سطر اوّل ورودی، به ترتیب اعداد ‎$n$‎ و ‎$k$‎ آمده‌اند. * ‎در سطر دوم به ترتیب ‎$s$‎ و ‎$t$‎ نوشته شده‌اند که ‎$1 \leq s,t \leq n$‎ و ‎$s \neq t$‎. * ‎سپس در ‎$n$‎ سطر، ماتریس مجاورت گراف به صورت یک ماتریس از $0$‎ و ‎$1$‎ آمده است. * در این ماتریس، عدد ‎$j$‎امِ سطر ‎$i$‎ام، ‎$1$‎ است اگر و تنها اگر $i \neq j$‎ و در گراف، یال جهت‌داری از رأس ‎$i$‎ام به را‎ٔس $j$‎ام وجود داشته باشد. * $2 \leq n \leq 100$‎. * $1 \leq k \leq 50$‎ ولی در ‎$30$‎ درصد تست‌ها ‎$k \leq 15$‎ است. ===== خروجی ===== * ‎در صورت وجود، کم‌ترین ‎$x$‎ای که ‎$x \leq k$‎ و هپید پس از پایان روز ‎$x$‎ام می‌تواند به مهدکودک برسد را چاپ کند. * ‎‎در غیر این‌صورت، یعنی اگر هپید نمی‌تواند تا آخر ‎$k$‎ روز به مهدکودک برسد، در خروجی پیام ‎happied is not happy را‎ چاپ کنید. ===== محدودیت‌ها ===== * محدودیت زمان: ۱ ثانیه * محدودیت حافظه: ۲۵۶ مگابایت ===== ورودی و خروجی نمونه ===== ^ ورودی نمونه ^ خروجی نمونه ^ |5 2 \\ 1 4 \\ ‎0 1 0 0 0 \\ 0 0 1 0 0 \\ 0 0 0 1 0 \\ 0 0 0 0 1 \\ 0 0 0 0 0 | 2 | |5 1 \\ 1 4 \\ 0 1 0 0 0 \\ 0 0 1 0 0 \\ 0 0 0 1 0 \\ 0 0 0 0 1 \\ ‎0 0 0 0 0 | happied is not happy | * [[سوال ۱۳|سوال بعد]] * [[سوال ۱۱|سوال قبل]] ‎‎ ‎‎