Županijska razina / Primjena algoritama OŠ 2021. / Osnovna škola (7. razred) - 3. zadatak

U sibirskom Jakutsku, koji slovi kao najhladniji grad na svijetu, temperature zimi redovito se spuštaju do - 50 stupnjeva celzijevih.

Unatoč tomu, grad ima skoro 300 000 stanovnika koji najnormalnije šeću okolo te čak voze i bicikle.

Autor ovog zadatka pretpostavlja da se tajna njihove otpornosti krije u zabavi s babuškama, tradicionalnim ruskim igračkama.

Mirko je nabavio N babuški veličina 1, 2, 3, … N i sada se želi njima igrati.

Svaka od babuški može se otvoriti, a unutar nje moguće je staviti bilo koju manju babušku, ali samo jednu, unutar koje može biti neka još manja babuška, a unutar nje još manja, i tako sve do najmanje babuške koju imamo.

Mirkove babuške na početku su poredane na stolu i sve su prazne, to jest nijedna nema neku drugu babušku u sebi.

Mirko će redom napraviti M promjena, a svaka promjena bit će oblika “STAVI X u Y”, a to znači da će Mirko odabrati neke dvije babuške, manju babušku veličine X i veću babušku veličine Y te zatim staviti babušku X u babušku Y.

Ako se babuška X već nalazi u nekoj babuški, Mirko će je najprije izvaditi.

U babuški X će i dalje ostati sve babuške koje su se nalazile unutar nje, ako takvih ima.

Odnos svih ostalih babuški ostat će nepromijenjen.

Nakon toga, ako je babuška Y prazna, Mirko će odmah staviti babušku X u nju.

Ako babuška Y nije prazna, to jest u sebi ima neku babušku Z, Mirko će prvo iz babuške Y izvaditi babušku Z, a tek onda u babušku Y staviti babušku X.

U babuški Z će i dalje ostati sve babuške koje su se nalazile unutar nje, ako takvih ima.

Odnos svih ostalih babuški ostat će nepromijenjen.

Nakon svih M promjena, ispiši ukupan broj babuški koje se ne nalaze unutar neke druge babuške. Dodatno, za svaku babušku ispiši koju babušku prvu trebamo otvoriti ako želimo doći do nje.

Primjerice, ako je babuška 1 unutar babuške 2, a babuška 2 unutar babuške 3, prva babuška koju trebamo otvoriti ako želimo doći do babuške 1 je babuška 3.

Ulazni podaci

U prvom su retku prirodni brojevi N i M (1 ≤ N, M, ≤ 10), broj babuški i broj promjena.

U sljedećih M redaka su po dva prirodna broja X i Y (1 ≤ X < Y ≤ N), brojevi iz teksta zadatka.

Izlazni podaci

U prvi redak ispiši ukupan broj babuški koje se ne nalaze unutar neke druge babuške.

U drugi redak ispiši N brojeva odvojenih razmacima, odgovore na pitanje iz teksta zadatka za babuške redom od 1 do N.

Ako za neku babušku ne treba otvoriti nijednu drugu kako bi se do nje došlo, za nju ispiši -1.

Primjer zadatka

Ulaz

3 2
1 2
2 3

Izlaz

1
3 3 -1

Objašnjenje

Opis prvog probnog primjera: Mirko će prvo staviti babušku 1 u babušku 2, a potom babušku 2 u babušku 3. Na kraju se samo babuška 3 ne nalazi unutar neke druge babuške te je ona ujedno i prva

babuška koju trebamo otvoriti ako želimo doći do babuški 1 i 2.

Ulaz

5 4
3 5
1 3
2 4
2 3

Izlaz

3
-1 5 5 -1 -1

Objašnjenje

Opis drugog probnog primjera: Mirko će prvo staviti babušku 3 u babušku 5, a potom babušku 1 u babušku 3. Nakon toga će staviti babušku 2 u babušku 4. Raspored babuški je onda [(1 u 3 u 5), (2 u 4)]. Da bi napravio sljedeću promjenu, tj. stavio babušku 2 u babušku 3, najprije mora babušku 2 izvaditi iz babuške 4, a potom iz babuške 3 izvaditi babušku 1. Nakon što je to učinio, stavlja babušku 2 u babušku 3.

Konačni raspored babuški je [(1), (2 u 3 u 5), (4)].

Ulaz

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

Izlaz

2
8 7 8 7 7 8 -1 -1

Objašnjenje

Opis trećeg probnog primjera: Raspored prije stavljanja 4 u 5 je [(1 u 3 u 5 u 7), (2 u 4 u 6 u 8)]. Nakon stavljanja 4 u 5, raspored je [(1 u 3), (2 u 4 u 5 u 7), (6 u 8)]. Nakon stavljanja 3 u 6, konačni raspored je [(1 u 3 u 6 u 8), (2 u 4 u 5 u 7)].