% Idee: Arkadiusz Czarkowski, Bartłomiej Czarkowski
% Tekst: Arkadiusz Czarkowski, Bartłomiej Czarkowski, Ahto Truu

\documentclass[a4paper,11pt]{article}
\usepackage[et]{../../eio}

\begin{document}
\begin{ol}{\eio}{\vv 15.03.2026}{\yle}{}
\begin{yl}{1}{Agendid}{age}{1 sek / 3 sek}{100 punkti}

Bytelandis tegutseb grupp agente, kellest igaüks töötab ühel $M$ missioonist. Bytelandis on $N$ linna, mis on ühendatud $N-1$ maanteega, nii et nende maanteede kaudu on võimalik reisida igast linnast igasse teise linna. Maantee number $i$ ühendab linnu $A_i$ ja $B_i$ ning sellel tegutseb agent, kes töötab hetkel missioonil $X_i$. Samal missioonil võib töötada mitu agenti.

Sinu ülesanne on hallata, millise missiooniga iga agent tegeleb. Geopoliitilise olukorra järsu muutuse tõttu oled otsustanud, et maanteel number $i$ tegutsev agent peaks nüüd töötama missioonil~$Y_i$. Sa edastad selle teabe agentidele spetsiaalsete sõnumite abil. Iga sõnum on arvude $1$ kuni $M$ permutatsioon $P$. (Antud jada permutatsioon on iga jada, mis sisaldab samu arve kui algne jada, kuid potentsiaalselt erinevas järjekorras.)

Sõnumi oma agentidele edastamiseks valid alamhulga linnu, kus sõbralikud kohalikud elanikud hommikul permutatsiooni $P$ välja panevad. Päeva jooksul külastab iga agent linnu oma maantee mõlemas otsas ning muudab oma missiooni siis ja ainult siis, kui permutatsioon väljas mõlemas linnas. Kui agendi praegune missioon on $c$ ja ta oma missiooni muudab, siis hakkab ta pärast muudatust tööle missioonil $P_c$. Õhtul eemaldavad samad sõbralikud elanikud oma linna välja panud sõnumid.

Asi on kiireloomuline, seega soovid hoida sõnumite arvu väikesena. Leia sõnumite jada, mis võimaldab selle eesmärgi saavutada.

\sis
Sisendi esimesel real on kaks täisarvu $N$ ja $M$ ($1 \le N \le 50\,000$, $1 \le M \le 32$), vastavalt linnade arv Bytelandis ja missioonide arv. Järgmisel $N-1$ real on igaühel neli täisarvu $A_i$, $B_i$, $X_i$, $Y_i$ ($1 \le A_i, B_i \le N$, $1 \le X_i, Y_i \le M$), mis tähendavad, et linnade $A_i$ ja $B_i$ vahel on maantee ning sellel maanteel tegutsev agent töötab praegu missioonil $X_i$ ja peaks edaspidi töötama missioonil~$Y_i$.

\val
Esimesele reale väljastada üks mittenegatiivne täisarv $K$, sõnumite arv. Järgmisele $K$ reale väljastada sõnumite kirjeldused, igaüks eraldi reale. Permutatsiooni $P$ avaldamist $L$ linnas $V_1, \ldots, V_L$ kirjeldus on tühikutega eraldatud täisarvude jada $P_1, P_2, \ldots, P_M, L, V_1, V_2, \ldots, V_L$. Arvud $V_1, \ldots, V_L$ peavad olema paarikaupa erinevad. Kui sobivaid sõnumijadasid on mitu, väljastada ükskõik milline neist.

\nde[0]{3cm}{6cm}

Esimene permutatsioon $(1, 3, 2, 4)$ pannakse välja kõigis linnades, seega kõik agendid missioonil~2 lülituvad missioonile~3 ja kõik agendid missioonil~3 lülituvad missioonile~2. Teine permutatsioon $(3, 1, 2, 4)$ pannakse välja linnades 1, 6, 5 ja~3. Agent maanteel~1--3 lülitub missioonilt~1 missioonile~3, agent maanteel~3--5 missioonilt~2 missioonile~1 ja agent maanteel~3--6 missioonilt~3 missioonile~2. Viimane permutatsioon suunab maanteel~1--4 tegusteva agendi missioonilt~3 missioonile~4.

\clearpage

\hnd \testidgrupis
\begin{xenum0}
  \item (0 punkti) \naitedlyhem
  \item (4 punkti) $N \le 10$.
  \item (32 punkti) $A_i = i$, $B_i = N$ iga $1 \le i < N$ korral.
  \item (12 punkti) $M = 2^s$, kus $s$ on mingi mittenegatiive täisarv.
  \item (12 punkti) $A_i = i$, $B_i = i + 1$ iga $1 \le i < N$ korral.
  \item (40 punkti) \piiranguteta
\end{xenum0}

Lahenduse skoori igas testigrupis määrab suurim sõnumite arv (allolevas tabelis tähistatud kui $\max(K)$), mida lahendus selle rühma mõnes testis kasutas:

\begin{center}
\begin{tabular}{c|c}
 \textbf{Sõnumeid}        & \textbf{Skoor} \\
 \hline
 $0 \le \max(K) \le 10$   & 100\% \\
 $11 \le \max(K) \le 15$  & 85\% \\
 $16 \le \max(K) \le 20$  & 65\% \\
 $21 \le \max(K) \le 30$  & 50\% \\
 $31 \le \max(K) \le 65$  & 25\% \\
 $66 \le \max(K) \le 100$ & 20\% \\
 $101 \le \max(K)$        & 0\%
\end{tabular}
\end{center}

Liigse hindamisaja vältimiseks saab iga väljund, kus $K > 1\,000$, alati diagnoosi ``Vale vastus'', ilma kontrollimata, kas sõnumijada saavutab eesmärgi või mitte.

Selles ülesandes on lahendustel lubatud tavapärase 256 MB asemel kasutada 1 GB mälu.

\end{yl}
\end{ol}
\end{document}
