- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
قرار است یک تورنومنت کشتی با \(n\) شرکتکننده برگزار شود. شرکتکنندگان را با اعداد \(1\) تا \(n\) نامگذاری میکنیم. در این تورنومنت هر دو شرکتکننده دقیقاً یک بار با هم بازی میکنند (در کل \( \frac{n(n-1)}{2} \) بازی انجام خواهد شد) و هر شرکتکننده در یک روز حداکثر یک بازی میتواند انجام دهد. شرکتکنندگان فکر میکنند اگر به ترتیب خاصی با حریفان خود بازی کنند، شانس بیشتری برای قهرمانی خواهند داشت. به طور دقیق، هر شرکتکننده نام ترتیب زیر را برای بازی با شرکتکنندگان دیگر ترجیح میدهد:
\[ P_{i,1}, P_{i,2}, \dots, P_{i,n-2}, P_{i,n-1} \]
برگزارکننده تورنومنت که میخواهد همه شرکتکنندگان راضی باشند، از شما میخواهد که به او بگویید آیا میتوان برنامه بازیها را به گونهای چید که همه شرکتکنندگان به ترتیب دلخواه خود بازی کنند یا خیر. اگر جواب مثبت است، به او بگویید حداقل چند روز برای برگزاری تورنومنت لازم است.
ورودی
در خط اول ورودی \(n\) که تعداد شرکتکنندگان است داده میشود.
سپس، به ازای هر \(1 \leq i \leq n\)، در \((i+1)\)امین خط ورودی که مرتبط با شرکتکننده \(i\)ام است، جایگشتی از \(1\) تا \(n-1\) شرکتکنندهی دیگر داده میشود که بیانگر ترتیب مطلوب شرکتکننده \(i\)ام است.
خروجی
در تنها خط خروجی، اگر برگزاری این تورنومنت ممکن است کمترین تعداد روز لازم و در غیر این صورت −۱ چاپ کنید.
محدودیتها
- \(3 \leq n \leq 1000\)
مثالها
ورودی نمونه ۱
3
2 3
1 3
1 2
خروجی نمونه ۱
3
ورودی نمونه ۲
4
4 2 3
3 4 1
2 4 1
1 2 3
خروجی نمونه ۲
4
ورودی نمونه ۳
3
3 2
1 3
2 1
خروجی نمونه ۳
-1