Бұл — көп кезеңді (multi-pass) есеп.
Кивотостың цифрлық мұрағаттарында Плана (Plana) Битемпоралды Логтар деп аталатын құпия жазбалар жинағын тапты. Әрбір лог түбірлі ағашты құрайтын, $1$-ден $n$-ге дейін нөмірленген $n$ жазбадан тұрады. Алайда уақыт ағыны ретроспективті (A логикасы) немесе перспективті (B логикасы) болуына байланысты құрылымдық шектеулер әртүрлі болады:
- A логикасы: Ағаштың түбірі $1$-жазбада орналасқан; кез келген басқа $i$ жазбасының $p_i < i$ болатындай $p_i$ ата-анасы бар.
- B логикасы: Ағаштың түбірі $n$-жазбада орналасқан; кез келген басқа $i$ жазбасының $q_i > i$ болатындай $q_i$ ата-анасы бар.
Құрылымдық қасиеттерді талдау үшін Плана жазбалардың екі түрін анықтайды:
- Терминал (Terminal): Ешбір басқа жазбаға ата-ана болмайтын жазба.
- Хаб (Hub): Кемінде бір басқа жазбаға ата-ана болатын жазба.
Плана Логикалық резонанс (Logical Resonance) деп аталатын мінсіз симметрияны байқады. Бұл қасиет A логикасының логы мен B логикасының логы арасында келесі шарт орындалғанда және тек сонда ғана орындалады:
$$\text{For every } i\text{, entry } i \text{ is a Terminal in Logic A} \iff \text{entry } i \text{ is a Hub in Logic B.}$$
Плана осы шектеу кезінде жарамды A логикасы логтары мен B логикасы логтарының саны бірдей екенін математикалық түрде дәлелдеді. Енді ол сізге бір лог форматын екіншісіне түрлендіретін Әмбебап Аударма Хаттамасын — биекцияны — құрастыруды тапсырады.
Дұрыстықты бағалау
Сіздің шешіміңіз әр тестте екі рет іске қосылады. Бірінші іске қосуда шешіміңіз әрбір A логикасының логын Логикалық резонанс шартын қанағаттандыратын B логикасының логына түрлендіруі керек. Екінші іске қосуда, бірінші іске қосуыңыз шығарған B логикасының логы берілгенде, шешіміңіз бастапқы A логикасының логын дәл қалпына келтіруі керек.
Екінші іске қосудың кірісі бірінші іске қосудағы шығысыңызбен бірдей B логикасының логтарынан тұрады, бірақ олардың реті басқаша болуы мүмкін. Екінші іске қосудағы әрбір кіріс B логикасының логы үшін оған сәйкес келетін A логикасының логын шығаруыңыз керек. Егер осындай әрбір B логикасының логы үшін сіздің шығысыңыз бірінші іске қосуда оны тудырған A логикасының логымен дәлме-дәл сәйкес келсе, шешіміңіз дұрыс деп есептеледі.
Шешіміңізді әзірлеуге және тексеруге көмектесу үшін тестілеу құралы ұсынылады.
Кіріс деректер
Кірістің бірінші жолында іске қосу нөмірін және тест жиынтықтарының санын білдіретін екі бүтін $r$ ($r \in \{1, 2\}$) және $T$ ($1 \le T \le 10^5$) сандары берілген.
Әрбір тест жиынтығы үшін бірінші жолда бүтін $n$ ($2 \le n \le 10^3$) саны берілген.
Егер $r = 1$ болса, екінші жолда A логикасының логын білдіретін $n$ бүтін $p_1, p_2, \dots, p_n$ сандары берілген. $p_1 = 0$ екеніне, ал $2 \le i \le n$ үшін $1 \le p_i < i$ — $i$ жазбасы жалғанған жазба екеніне кепілдік беріледі. Мұнда біз $0$ санын жазбаның ата-анасы жоқ екенін (яғни ол түбір екенін) белгілеу үшін қолданамыз.
Әйтпесе, егер $r = 2$ болса, екінші жолда B логикасының логын білдіретін $n$ бүтін $q_1, q_2, \dots, q_n$ сандары берілген. $q_n = 0$ екеніне, ал $1 \le i \le n - 1$ үшін $i < q_i \le n$ — $i$ жазбасы жалғанған жазба екеніне кепілдік беріледі.
Барлық тест жиынтықтары бойынша $n^2$ мәндерінің қосындысы $10^7$ шамасынан аспайтынына кепілдік беріледі.
Шығыс деректер
Егер $r = 1$ болса, әрбір тест жиынтығы үшін түрлендірілген B логикасының логын білдіретін, бос орынмен бөлінген $n$ бүтін $q_1, q_2, \dots, q_n$ сандарын шығарыңыз. $q_n = 0$ және $1 \le i \le n - 1$ үшін $i < q_i \le n$ болуы тиіс. Логикалық резонанс қасиеті орындалуы керек: $i$ жазбасы A логикасында Терминал болады сонда және тек сонда ғана, егер $i$ жазбасы B логикасында Хаб болса.
Әйтпесе, егер $r = 2$ болса, әрбір тест жиынтығы үшін қалпына келтірілген A логикасының логын білдіретін, бос орынмен бөлінген $n$ бүтін $p_1, p_2, \dots, p_n$ сандарын шығарыңыз.
Мысал
1-мысал, 1-өту
Кіріс деректер
1 3 4 0 1 1 2 4 0 1 2 1 4 0 1 1 1
Шығыс деректер
3 3 4 0 3 4 4 0 2 3 4 0
1-мысал, 2-өту
Кіріс деректер
2 3 4 2 3 4 0 4 3 3 4 0 4 3 4 4 0
Шығыс деректер
0 1 1 1 0 1 1 2 0 1 2 1
1-мысалға түсініктеме
Ықтимал жарамды биекция төменде көрсетілген.
