broscute

Pe un lac cu apă termală se află $n+1$ frunze de nuferi. Pe $n$ dintre ele stau la soare $n$ broscuţe. Evident, o frunză este liberă şi broscuţele au început să se joace. În fiecare moment o broscuţă sare de pe frunza ei pe frunza liberă din acel moment.

Cerinţă

Numerotând frunzele de la $1$ la $n+1$, broscuţele de la $1$ la $n$, şi cunoscându-se ordinea iniţială a broscuţelor pe cele $n+1$ frunze, să se determine numărul minim de sărituri ale broscuţelor de pe o frunză pe alta, astfel încât ele să se găsească într-o ordine finală, dată, precum şi săriturile realizate.

Date de intrare

Fişierul de intrare broscute.in conţine pe prima linie un număr natural $n$ reprezentând numărul de broscuţe separat printr-un spaţiu de un număr natural $t$, care reprezintă cerinţa: $1$, dacă se cere numărul de sărituri, respectiv $2$ dacă se cere ordinea săriturilor. Linia a doua conţine $n+1$ numere naturale reprezentând configuraţia iniţială a broscuţelor pe cele $n+1$ frunze, iar linia a treia conţine $n+1$ numere naturale reprezentând configuraţia finală a broscuţelor pe cele $n+1$ frunze.

Date de ieşire

Fişierul de ieşire broscute.out va conţine pe prima linie un număr natural $k$ ce reprezintă numărul minim de sărituri, dacă cerinţa este $1$. Dacă cerinţa este $2$ fişierul de ieşire va conţine mai multe linii, pe fiecare dintre ele existând $3$ numere naturale $b \ s \ d$, separate prin câte un spaţiu, care descriu săritura, reprezentând numărul broscuţei $b$, frunza de pe care sare $s$ şi frunza pe care sare $d$. În cazul în care la cerinţa $2$ broscuţele nu fac nici o săritură se va afişa pe prima linie mesajul broscutele nu se joaca.

Restricţii şi precizări

• $2 \leq n \leq 1\ 000$
• În descrierea configuraţiilor din fişierul de intrare frunza liberă este reprezentată prin valoarea $0$
• Pentru cerința $1$ se acordă $50\%$ din punctaj, iar pentru cerința $2$ tot $50\%$ din punctaj.
• În cazul în care cerința este $2$ și numărul de sărituri afișate nu este minim dar realizează ajungerea la configurația finală se acordă doar $30\%$ din punctaj.

Exemplul 1

broscute.in

4 2
3 2 0 1 4
1 2 3 4 0

broscute.out

3 1 3 
1 4 1 
4 5 4

Explicație

Sunt $4$ broscuţe, deci $5$ frunze de nufăr. Cerinţa este $2$.
Broscuţele vor face $3$ sărituri:

• broscuţa $3$ sare de pe frunza $1$ pe frunza $3$
• broscuţa $1$ sare de pe frunza $4$ pe frunza $1$
• broscuţa $4$ sare de pe frunza $5$ pe frunza $4$

Exemplul 2

broscute.in

4 1
3 2 0 1 4
1 2 3 4 0

broscute.out

3

Exemplul 3

broscute.in

4 2
3 2 0 1 4
3 2 0 1 4

broscute.out

broscutele nu se joaca