C. Хуваарилалт

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

2500 онд Кайро дахь Герман их сургуулийн (КГИС) төгсөлтийн баярын ёслол болж байв.

Төгсөлтийн баярын хамгийн чухал ажлын нэг бол профессоруудыг ёслолын танхимд хуваарилах юм.

Уламжлалт ёсоор КГИС $n$ профессортой. Профессор болгон албан тушаалын түвшинтэй ба бүгд ялгаатай. Профессорууыг $1$-ээс $n$ хүртэл дугаарлаад, хамгийн хүндтэй албан тушаалыг $1$ гээд, хамгийн бага хүндтэй албан тушаалыг $n$ гэе.

Ёслолын танхим $n$ суудалтай, профессор болгонд нэг суудал оногддог. Тэд танхим дахь зарим суудлууд илүү албан тушаалтай хүн суух ёстой гэж боддог. Илүү дэлгэрэнгүйгээр, $m$ хос суудал "их-бага" ажлын тушаалын шүтэлцээтэй байдаг ба $(a_{i}, b_{i})$ суудлуудад сууж байгаа профессоруудын хувьд a_{i} суудалд сууж байгаа профессорын албан тушаал b_{i} суудалд сууж байгаа профессорын албан тушаалаас их байх ёстой юм.

КГИС уламжлалаа чандлан сахидаг ба энэ нь 2001 оноос эхэлж ажиглагдсан юм. Энэхүү уламжлал нь : * Жил болгон профессоруудын суудал өөрчлөгддөг * 2001 онд суудлууд нь цагаан толгойн хамгийн эхний хуваарилалт байсан * Дараалалсан жил болгоны дараагийн жил нь цагаан толгойн дарааллын дараагийн хуваарилалт байна

Профессоруудын хуваарилалтыг эхний суудалд сууж байгаа профессорын албан тушаал, хоёрдах суудалд сууж байгаа профессорын албан тушаал, г.м-ээр $n$ тоогоор дүрслэнэ.

Таньд $n$, профессоруудын тоо, $y$, одоогийн жил ба $m$, "их-бага" албан тушаалын шүтэлцээтэй суудлын тоо өгөгдсөн бол өгөдсөн жил болоход профессоруудыг яаж хуваарилахыг олно уу.

Оролт

Эхний мөрөнд гурван бүхэл тоо болох $n$, $y$ ба $m$ ($1 ≤ n ≤ 16, 2001 ≤ y ≤ 10^{18}, 0 ≤ m ≤ 100$) - профессроуудын тоо, одоогийн жил, "их-бага" албан тушаалын шүтэлцээтэй суудлын тоо.

Дараагийн $m$ мөрөнд хос тоо өгөгдөнө, "$a_{i}$ $b_{i}$", $a_{i}$-р суудалд сууж байгаа профессорын албан тушаал $b_{i}$-р суудалд сууж байгаа профессорын албан тушаалаас их байх ёстой. ($1 ≤ a_{i}, b_{i} ≤ n, a_{i} ≠ b_{i}$). Зарим хосууд нэгээс олон удаа орж болно.

C++ хэл дээр 64-битийн тоо хэрэглэх үед %lld-г хэрэглэхгүй байхыг зөвлөж байна. %I64d эсвэл cin, cout стриймийг ашиглана уу.

Гаралт

Өгөдсөн жил болоход профессоруудыг яаж хуваарилахыг хэвлэ. Хэрэв хуваарилалт хийх боломжгүй буюу бүх боломж шавхагдвал "The times have changed"(хашилтгүйгээр) гэж хэвлэнэ үү.

Орчуулсан: Б.Алтангэрэл

Жишээ тэстүүд

Оролт
3 2001 2
1 2
2 3
Гаралт
1 2 3
Оролт
7 2020 6
1 2
1 3
2 4
2 5
3 6
3 7
Гаралт
1 2 3 7 4 6 5
Оролт
10 3630801 0
Гаралт
The times have changed
Оролт
3 2001 3
1 2
2 3
3 1
Гаралт
The times have changed

Тэмдэглэл

Эхний жишээн дээр хуваарилалт цагаан толгойн дарааллаар эхнийх нь болох 1 2 3 байна.

Гуравдахь жишээн дээр КГИС-н хуваарилалт 3630800 оны дараа дуусах болно.

Дөрөв дэх жишээн дээр боломжит хуваарилалт олдохгүй.

Цагаан толгойн харьцуулалтыг орчин үеийн програмчлалын хэл дээр < operator-р гүйцэтгэсэн байдаг ба хуваарилалт $a$ нь цагаан толгойн дарааллаар хуваарилалт $b$-с бага байхын тулд $a_{i} < b_{i}$ ба ($1 ≤ j < i$) байх бүх $j$-н хувьд $a_{j} = b_{j}$ байдаг $i$ ($1 ≤ i ≤ n$) олдоно.

Сэтгэгдлүүдийг ачааллаж байна...