Hardwarové a softwarové komponenty počítačových systémů jsou na sobě často závislé -- jiné komponenty musí být nainstalovány napřed, aby všechno bezchybně fungovalo, jedna komponenta je často potřebná pro činnost několika jinných. Například jak program TELNET, tak program FTP vyžadují přítomnost modulu TCP/IP. Pokud nainstalujete TCP/IP a TELNET a později se rozhodnete přidat FTP, není nutné instalovat znovu modul TCP/IP.

V některých případech by reinstalace či vícenásobná instalace některých komponent znamenala jen plýtvání zdroji (například pamětí), u jiných (jako TCP/IP) by to mohlo vést ke ztrátě konfiguračních informací.

Je užitečné umět odstranit komponenty které již nejsou potřeba. Pak je někdy možné odstranit i další komponenty, a to takové, které byly potřeba pouze kvůli závislostem na právě odinstalované. Ušetříme tím místo na disku, v paměti a někdy i další prostředky. Samozřejmě ale není možné takto automaticky odinstalovat komponentu, na které závisí některá další, nebo kterou jsme nainstalovali explicitně. Příklad: Odstraněním FTP a TCP/IP bychom znemožnili funkci programu TELNET. Podobně, odinstalováním TCP/IP by zneschopnilo jak TELNET, tak FTP. Naopak, pokud bychom si nainstalovali TCP/IP podporu pro svojí vlastní potřebu, pak přidali TELNET a nakonec TELNET opět odebrali, měl by TCP/IP modul zůstat nainstalován.

Vaším úkolem je automatizovat proces přidávání a odebírání komponent. Komponenta má být nainstalována pokud o to uživatel požádá, nebo pokud je potřeba pro správnou činnost jiné komponenty, která je zrovna instalována. Komponenta instalovaná na pokyn uživatele smí být odinstalována opět jen na jeho pokyn. Komponenta nainstalovaná automaticky má být odstraněna pokud již není potřeba.

Specifikace vstupu

Vstup se skládá z N zadání. První řádek vstupu obsahuje pouze celé kladné číslo N. Dále následují jednotlivá zadání. Každé zadání bude obsahovat posloupnost příkazů (viz níže), každý na zvláštní řádce obsahující méně než 80 znaků. Jména komponent nejsou delší než 10 znaků, velká/malá písmena jsou významná. Jména příkazů (DEPEND, INSTALL, REMOVE a LIST) budou psána vždy velkými písmeny počínaje prvním znakem řádku. Za jménem příkazu mohou následovat jména komponent, od příkazu a od sebe navzájem budou oddělena jednou mezerou. Všechny potřebné příkazy DEPEND budou předcházet příkazy INSTALL, které je používají. Závislosti komponent netvoří smyčky. Celkový počet komponent je maximálně 5000. Konec zadání je označen řádkou se slovem END. Na další řádce pak začíná nové zadání, je-li nějaké.

Seznam příkazů:	význam:
DEPEND x1 x2 [x3 ...]	Komponenta x1 závisí na x2, příp. x3 ... Žádné dva příkazy DEPEND nebudou mít shodné x1
INSTALL x1	Nainstaluj x1, příp. další komponenty potřebné k činnosti x1
REMOVE x2	Odeber x2, příp. další komponenty, které se tím stanou nepotřebné
LIST	Vypiš seznam v tomto okamžiku nainstalovaných komponent v abecedním pořadí.

Specifikace výstupu

Ke každému příkazu INSTALL či REMOVE vypište provedené akce, viz vzorový výstup. Závislosti mezi komponentami (dané předchozími příkazy DEPEND), nesmí být ani na chvíli porušeny. Všechny akce potřebné k vykonání příkazu uživatele musí být dokončeny před započetím zpracování následujícího příkazu. Je-li při zachování výše uvedených pravidel stále možné postupovat několika různými způsoby, vyberte ten, v němž jsou jména komponent lexikograficky nejmenší. (Posloupnost a je lexikograficky menší než posloupnost b, pokud první člen a je menší než první člen b, nebo pokud jsou první členy posloupností a,b shodné a zbytek posloupnosti a je lexikograficky menší než zbytek posloupnosti b.) K příkazu DEPEND a END nevypisujte nic. Je-li komponenta požadovaná v příkazu INSTALL již nainstalována, vypište: `X je jiz nainstalovan.' Taková komponenta se však začne považovat za explicitně nainstalovanou, a smí být tedy odstraněna jen na pokyn uživatele. Při chybném příkazu REMOVE vypište: `X je stale potreba.' případně `X neni instalovan.'.

Příklad vstupu

4
DEPEND A B
INSTALL A
INSTALL A
LIST
REMOVE B
REMOVE A
LIST
INSTALL B
LIST
END
DEPEND TELNET TCPIP NETCARD
DEPEND TCPIP NETCARD
DEPEND DNS TCPIP NETCARD
DEPEND BROWSER TCPIP HTML
INSTALL NETCARD
INSTALL TELNET
INSTALL foo
REMOVE NETCARD
INSTALL BROWSER
INSTALL DNS
LIST
REMOVE TELNET
REMOVE NETCARD
REMOVE DNS
REMOVE NETCARD
INSTALL NETCARD
REMOVE TCPIP
REMOVE BROWSER
REMOVE TCPIP
END
DEPEND a b r
DEPEND b c z
DEPEND r d e
INSTALL a
LIST
REMOVE a
LIST
END
DEPEND a b
INSTALL a
INSTALL b
REMOVE a
LIST
END

Instaluji B.
Instaluji A.
A je jiz nainstalovan.
A
B
B je stale potreba.
Odstranuji A.
Odstranuji B.
Instaluji B.
B
Instaluji NETCARD.
Instaluji TCPIP.
Instaluji TELNET.
Instaluji foo.
NETCARD je stale potreba.
Instaluji HTML.
Instaluji BROWSER.
Instaluji DNS.
BROWSER
DNS
HTML
NETCARD
TCPIP
TELNET
foo
Odstranuji TELNET.
NETCARD je stale potreba.
Odstranuji DNS.
NETCARD je stale potreba.
NETCARD je jiz nainstalovan.
TCPIP je stale potreba.
Odstranuji BROWSER.
Odstranuji HTML.
Odstranuji TCPIP.
TCPIP neni instalovan.
Instaluji c.
Instaluji d.
Instaluji e.
Instaluji r.
Instaluji z.
Instaluji b.
Instaluji a.
a
b
c
d
e
r
z
Odstranuji a.
Odstranuji b.
Odstranuji c.
Odstranuji r.
Odstranuji d.
Odstranuji e.
Odstranuji z.
Instaluji b.
Instaluji a.
b je jiz nainstalovan.
Odstranuji a.
b