Бұл — екі рет іске қосылатын (multi-pass) есеп.

VegiCat пен VegiDog $1$-ден $n$-ге дейін нөмірленген $n$ төбесі және $m$ қыры бар орманмен ойын ойнайды. Орман дегеніміз — циклі жоқ бағытталмаған граф. Ол міндетті түрде байланысқан емес.

Бірінші кезеңде VegiCat әрбір $u$ төбесіне $a_u$ ($1 \le a_u \le 2n$) бүтін санын меншіктейді. Мәндер қайталануы мүмкін.

VegiCat мәндерді меншіктеп болғаннан кейін төбелер қайта нөмірленеді. $p_1, p_2, \ldots, p_n$ арқылы $1, 2, \ldots, n$ сандарының орын алмастыруын белгілейік, мұнда $1$-ден $n$-ге дейінгі әрбір бүтін сан дәл бір рет кездеседі. Әрбір $u$ үшін бастапқыда $u$ нөмірі болған төбе енді $p_u$ нөмірін алады.

Әрбір $(u, v)$ қыры $(p_u, p_v)$ қырына айналады. Әр төбе өзіне меншіктелген мәнді сақтап қалады. Қайта нөмірлеуден кейін $i$ төбесіндегі мәнді $b_i$ деп белгілейік. Сонда $b_{p_u} = a_u$.

Екінші кезеңде VegiDog бастапқы орманды да, $p$ орын алмастыруын да білмей, тек $n$ санын және $b_1, b_2, \ldots, b_n$ мәндерін ғана алады. Ол жаңа төбе нөмірлерін пайдаланып барлық қырларды қалпына келтіруі керек.

Кез келген дұрыс орман және кез келген $p$ орын алмастыруы үшін жұмыс істейтін екі ойыншыға арналған стратегияларды құрастырыңыз.

Кіріс деректер

Сіздің программаңыз екі рет іске қосылады: алдымен VegiCat ретінде, содан кейін VegiDog ретінде. Тесттер екі іске қосуда да бірдей ретпен беріледі.

Бірінші іске қосу. Бірінші жолда сіздің VegiCat ретінде ойнайтыныңызды білдіретін cat жолы берілген.

Екінші жолда тесттер санын білдіретін бүтін сан $T$ ($1 \le T \le 10^4$) берілген. Одан кейін тесттердің сипаттамасы беріледі.

Әр тесттің бірінші жолында төбелер мен қырлар санын білдіретін екі бүтін сан $n$ мен $m$ ($1 \le n \le 2 \cdot 10^5$, $0 \le m < n$) берілген.

Келесі $m$ жолдың әрқайсысында $u$ мен $v$ төбелерінің арасындағы бағытталмаған қырды сипаттайтын екі бүтін сан $u$ мен $v$ ($1 \le u, v \le n$, $u \ne v$) берілген.

Графта циклдер немесе еселі қырлар жоқ екеніне кепілдік беріледі.

Барлық тесттер бойынша $n$ мәндерінің қосындысы $2 \cdot 10^5$-тен аспайтынына кепілдік беріледі.

Екінші іске қосу. Бірінші жолда сіздің VegiDog ретінде ойнайтыныңызды білдіретін dog жолы берілген.

Екінші жолда тесттер санын білдіретін бүтін сан $T$ ($1 \le T \le 10^4$) берілген. Одан кейін тесттердің сипаттамасы беріледі.

Әр тесттің бірінші жолында төбелер санын білдіретін бүтін сан $n$ ($1 \le n \le 2 \cdot 10^5$) берілген.

Екінші жолда жаңа төбелер ретімен меншіктелген мәндерді білдіретін $n$ бүтін сан $b_1, b_2, \ldots, b_n$ ($1 \le b_i \le 2n$) берілген.

Барлық тесттер бойынша $n$ мәндерінің қосындысы $2 \cdot 10^5$-тен аспайтынына кепілдік беріледі.

Шығыс деректер

Бірінші іске қосу. Әр тест үшін бір жолға $n$ бүтін санды $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 2n$) шығарыңыз. $a_i$ бүтін саны — $i$ төбесіне меншіктелген мән.

Екінші іске қосу. Әр тест үшін бірінші жолға қырлар санын білдіретін бүтін сан $m$-ді шығарыңыз. Келесі $m$ жолдың әрқайсысында жаңа төбе нөмірлері арқылы қырды сипаттайтын екі бүтін сан $u$ мен $v$ ($1 \le u, v \le n$, $u \ne v$) болуы керек.

Әр қырды кез келген ретпен бір реттен шығарыңыз. Қырдың кез келген ұшы бірінші жазылуы мүмкін. Егер $m = 0$ болса, тек $0$ санын шығарыңыз.

Мысалдар

Кіріс деректер 1

cat
4
1 0
4 3
1 2
4 3
2 3
7 2
6 4
7 1
10 7
10 9
7 9
10 5
4 8
3 7
4 10
1 2

Шығыс деректер 1

1
2 5 8 5
11 11 4 11 3 7 2
10 13 12 5 3 2 16 6 19 3

Кіріс деректер 2

dog
4
1
1
4
5 2 5 8
7
11 7 2 11 11 3 4
10
16 3 13 5 10 12 19 6 2 3

Шығыс деректер 2

0
3
1 4
2 1
4 3
2
4 3
5 2
7
1 7
4 8
5 3
6 1
7 10
10 2
10 4

Ескертпе

Бірінші тестте орманда бір төбе бар және қырлар жоқ. VegiCat төбеге $1$ мәнін меншіктейді, ал VegiDog $0$ шығарады.

Соңғы тестте орын алмастыру $p = [5, 3, 6, 4, 2, 9, 1, 8, 7, 10]$ болады.

VegiCat $a_7 = 16$ мәнін меншіктейді. $p_7 = 1$ болғандықтан, VegiDog $b_1 = 16$ мәнін алады.

Бастапқы $(3, 7)$ қыры $(p_3, p_7) = (6, 1)$ қырына айналады.

Бастапқы $(4, 10)$ қыры $(p_4, p_{10}) = (4, 10)$ қырына айналады. Мысалда бұл қыр $(10, 4)$ ретінде шығарылған, ол сол бағытталмаған қырдың өзін білдіреді.

Мысал кіріс және шығыс деректер пішімін көрсетеді. Оның жауаптары көрсетілген графтар мен орын алмастырулар үшін дұрыс. Алайда мысалдағы меншіктеулер кез келген дұрыс орман мен кез келген орын алмастыру үшін жұмыс істейтін стратегияның бөлігі болуына кепілдік берілмейді.