Կառուցում ենք կատարյալ զանգված
Դուք օգնում եք համակարգչային գիտությամբ զբաղվող ընկերոջդ մի հետազոտական նախագծում։ Այդ նախագծի նպատակը գտնել է այնպիսի a զանգված, որը բավարարում է որոշակի սահմանափակումների։ Մասնավորապես, ձեզ տրված են
p զույգ ինդեքսներ i և j, որտեղ i և j վերաբերում են a զանգվածի n երկարությանը։ Յուրաքանչյուր (i, j) զույգ սահմանում է պայման, որ պետք է փոքր լինի -ից։ Ձեր առաջադրանքն է գտնել a զանգված, որը կհամապատասխանի բոլոր այդ սահմանափակումներին։a զանգվածի ամբողջ թվերը պետք է լինեն 1-ից մինչև ներառյալ։
Մուտք
Մուտքի առաջին տողում տրված են երկու ամբողջ թվեր
n (2 ≤ n ≤ ) և p (1 ≤ p ≤ ), որտեղ n-ը a զանգվածի երկարությունն է, իսկ p-ն այն զույգերի քանակը, որոնք սահմանում են տարբեր a_i < a_j պայմաններ։Ելք
Եթե հնարավոր է գտնել a զանգված, որը բավարարում է բոլոր սահմանափակումներին, ծրագիրը պետք է տպի մեկ տող, որտեղ կլինեն
n ամբողջ թվեր (բացատներով բաժանված), որոնք համապատասխանեցնում են a զանգվածը։ Այդ թվերը պետք է գտնվեն [1, ] միջակայքում։Եթե գոյություն ունեն բազմաթիվ լուծումներ, կարելի է տպել ցանկացածը։
Օրինակներ
Մուտք | Ելք |
4 2
1 2
4 1 | 2 3 4 1 |
5 5
1 2
2 3
3 4
5 4
2 5 | 2 4 6 8 5 |
3 3
1 2
2 3
3 1 | Impossible |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB