فرض کنید گرافی $n$ راسی تهی دارید. در هر مرحله یک زیرگراف $k$ راسی از گراف را می‌گیریم و آنرا کامل می‌کنیم. پس از انجام تمام مراحل، فاصله‌ی راس $1$ تا $n$ را به دست آورید.

• به ترتیب $n$، $k$ و $m$ که $m$ تعداد زیرگراف‌های انتخابی‌ست.
• در $m$ خط بعد در هر خط $k‌$ عدد آمده است که هر‌کدام نشان‌دهنده‌ی راس‌های یک زیرگراف است.
• $1 \leq n \leq 10^6$
• $1 \leq m, k \leq 1000$

• کم‌ترین فاصله‌ی راس $1$ از $n$ را به‌دست آورید.
• اگر مسیری وجود ندارد $-1$ چاپ کنید.

• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

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