تاکسیک‌علیش


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

علیش که دیگه هدفی واسه زندگی‌کردن نداره تصمیم گرفته مریض‌شه. اما آقا مجید (که داره دکتر می‌شه) بهش گفته که باید nn تا قرص بخوره. علیش هم که به این سادگی نمی‌خواد قبول کنه mm تا شرط واسه قرص خوردن داره که هر شرط شامل aia_i و bib_i است که یعنی قرص aia_iام رو باید قبل قرص bib_iام بخوره. هم‌چنین nn شرط دیگه هم داره که قرص iiام باید حداقل lil_iامین و حداکثر rir_iامین قرصی باشه که می‌خوره. یه ترتیبی به علیش بدید که اگه به این ترتیب قرصاشو بخوره همه شرط‌ها برقرار باشه.

ورودی🔗

در خط اول nn و mm آمده که با یک فاصله از هم جدا شده‌اند.

در nn خط بعدی lil_i و rir_i ها آمده‌است.

در mm خط بعدی دو عدد aia_i و bib_i آمده که با فاصله از هم جدا شده اند و یعنی قرص aia_iام باید قبل قرص bib_iام خورده شود.

1n200 0001 \le n \le 200\ 000 1m300 0001 \le m \le 300\ 000 1lirin1 \le l_i \le r_i \le n 1aibin 1 \le a_i \le b_i \le n

خروجی🔗

در خروجی nn خط که شامل جایگشتی از اعداد ۱ تا nn است و تمام شروط در آن برقرار است چاپ شود. اگر چند جواب وجود داشت یکی را به دلخواه چاپ نمایید. اگر ترتیبی وجود نداشت که همه شرط‌ها در آن برقرار باشند -1 چاپ کنید.

مثال🔗

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

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

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

-1
Plain text

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

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

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

1
2
3
4
Plain text

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

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

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

1
4
3
2
Plain text