تورنمنت کشتی


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

قرار است یک تورنومنت کشتی با nn شرکت‌کننده برگزار شود. شرکت‌کنندگان را با اعداد 11 تا nn نام‌گذاری می‌کنیم. در این تورنومنت هر دو شرکت‌کننده دقیقاً یک بار با هم بازی می‌کنند (در کل n(n1)2 \frac{n(n-1)}{2} بازی انجام خواهد شد) و هر شرکت‌کننده در یک روز حداکثر یک بازی می‌تواند انجام دهد. شرکت‌کنندگان فکر می‌کنند اگر به ترتیب خاصی با حریفان خود بازی کنند، شانس بیشتری برای قهرمانی خواهند داشت. به طور دقیق، هر شرکت‌کننده نام ترتیب زیر را برای بازی با شرکت‌کنندگان دیگر ترجیح می‌دهد:

Pi,1,Pi,2,,Pi,n2,Pi,n1 P_{i,1}, P_{i,2}, \dots, P_{i,n-2}, P_{i,n-1}

برگزارکننده تورنومنت که می‌خواهد همه شرکت‌کنندگان راضی باشند، از شما می‌خواهد که به او بگویید آیا می‌توان برنامه بازی‌ها را به گونه‌ای چید که همه شرکت‌کنندگان به ترتیب دلخواه خود بازی کنند یا خیر. اگر جواب مثبت است، به او بگویید حداقل چند روز برای برگزاری تورنومنت لازم است.

ورودی🔗

در خط اول ورودی nn که تعداد شرکت‌کنندگان است داده می‌شود.
سپس، به ازای هر 1in1 \leq i \leq n، در (i+1)(i+1)امین خط ورودی که مرتبط با شرکت‌کننده iiام است، جایگشتی از 11 تا n1n-1 شرکت‌کننده‌ی دیگر داده می‌شود که بیانگر ترتیب مطلوب شرکت‌کننده iiام است.

خروجی🔗

در تنها خط خروجی، اگر برگزاری این تورنومنت ممکن است کمترین تعداد روز لازم و در غیر این صورت −۱ چاپ کنید.

محدودیت‌ها🔗

  • 3n10003 \leq n \leq 1000

مثال‌ها🔗

ورودی نمونه ۱🔗

3
2 3
1 3
1 2
Plain text

خروجی نمونه ۱🔗

3
Plain text

ورودی نمونه ۲🔗

4
4 2 3
3 4 1
2 4 1
1 2 3
Plain text

خروجی نمونه ۲🔗

4
Plain text

ورودی نمونه ۳🔗

3
3 2
1 3
2 1
Plain text

خروجی نمونه ۳🔗

-1
Plain text
ارسال پاسخ برای این سؤال
در حال حاضر شما دسترسی ندارید.