Radiotorņi

Kalnainā teritorijā izvietoti $N$ radiotorņi, kas sanumurēti ar naturāliem skaitļiem no $1$ līdz $N$. Šie torņi veido īpatnēju telekomunikācijas tīklu, kur signāls no viena torņa var tikt pārraidīts uz jebkuru citu radiotorni tieši vienā vienīgā veidā. Tīklu veido $N-1$ torņu pāru, kas savā starpā pārraida informāciju, savienojums.

Katram tornim $i (1 \leq i \leq N)$ ir piešķirta frekvence $f_i$, kurā tas pārraida signālu. Katram tornim signāla pārraides frekvence $f_i$ pieder frekvenču joslai, kurā pārraide ir visefektīvākā: $f_i \in [K, L]$.

Radiotorņu tīkls darbojas neoptimāli, ja tīklā ir viens vai vairāki frekvenču konflikti - t.i., eksistē torņu $(a, b)$ savienojums, kur $f_a = f_b$, jeb abi torņi signāla pārraidei izmanto vienu un to pašu frekvenci. Lai tā nebūtu, vienam vai vairākiem torņiem to signāla pārraides frekvenci var būt nepieciešams mainīt.

Signāla pārraides frekvences maiņa ir sarežģīta operācija, tāpēc katram radiotornim $i$ ir iespējams veikt šādu darbību ne vairāk kā vienreiz: palielināt vai samazināt $f_i$ uz attiecīgi $f_i+1$ vai $f_i-1$. Tomēr arī pēc šīs darbības veikšanas katra radiotorņa frekvencei jāpaliek labo frekvenču joslā $[K, L]$. Turklāt šo maiņu skaitam jābūt mazākajam iespējamajam.

Piemēram, 1. att. parādītajā tīklā (katra torņa frekvence ir atzīmēta uz bultiņām pie torņus apzīmējošajiem aplīšiem) visas frekvences atrodas frekvenču joslā $[3; 5]$ un ir trīs frekvenču konflikti: $4-6$, $4-3$ un $4-2$, kurus nav iespējams atrisināt, nomainot frekvenci tikai vienam no torņiem. Ja labo frekvenču joslā atrastos arī vērtība $2$, tad tas būtu iespējams, nomainot ceturtā torņa frekvenci no $3$ uz $2$. Bet tagad jānomaina divu torņu frekvences: ceturtā torņa frekvenci no $3$ uz $4$, bet piektā - no $4$ uz $3$ (2. att.).

Uzrakstiet datorprogrammu, kas realizē aprakstīto radiotorņu frekvenču maiņu, veicot mazāko nepieciešamo maiņu skaitu!

Pirmajā rindā doti trīs naturāli skaitļi: radiotorņu skaits $N$ ($2 \leq N \leq 5 \cdot 10^5$), frekvenču joslas kreisais $K$ ($K \geq 1$) un labais $L$ ($K < L \leq 10^9$) galapunkts. Otrajā rindā doti $N$ naturāli skaitļi - radiotorņu izmantotās frekvences. Katram $i$ ($1 \leq i \leq N$) $i$-tā radiotorņa izmantotā frekvence $f_i$ dota kā $i$-tais skaitlis rindā pēc kārtas. Zināms, ka visiem $i$ $f_i \in [K, L]$. Nākamajā $N-1$ ievaddatu rindā dots radiotorņu tīkla savienojumu apraksts - katrā no šīm rindām dots atšķirīgu naturālu skaitļu pāris - divu savienoto torņu numuri. Starp katriem diviem blakus skaitļiem ievaddatos ir tukšumzīme.

Izvaddatu pirmajā rindā jābūt veselam nenegatīvam skaitlim $S$ - mazākajam radiotorņu skaitam, kuru frekvences jāmaina, lai novērstu visus frekvenču konfliktus. Izvaddatu otrajā rindā jābūt $N$ naturāliem skaitļiem - radiotorņu izmantotajām frekvencēm pēc visu frekvenču konfliktu novēršanas. Katram $i$ ($1 \leq i \leq N$) $i$-tā radiotorņa izmantotā frekvence $f_i$ jāizvada kā $i$-tais skaitlis rindā pēc kārtas. Visiem $i$ jābūt spēkā $f_i \in [K, L]$. Starp katriem diviem blakus skaitļiem izvaddatos ir jābūt tukšumzīmei.