Shoda stromů

Dva neprázdné binární stromy T1 a T2 prohlásíme za shodné, pokud levý podstrom kořene T1 je shodný s levým podstromem kořene T2 a zároveň pravý podstrom kořene T1 je shodný s pravým podstromem kořene T2. Každé dva prázdné binární stromy budeme pokládat za shodné (nebo, chcete-li, budeme uvažovat, že existuje jediný prázdný binární strom, který je shodný sám se sebou).

Máme k dispozici dvě operace, jimiž lze měnit tvar libovolného binárního stromu. První oprací je operace SWAP(x) představující výměnu levého podstromu libovolného uzlu x ve stromu s pravým podstromem tohoto uzlu x. Druhou operaci je operace ROTL(x) představující standardní levou rotaci v libovolném uzlu x tak, jak je známa pro AVL stromy.

Naším úkolem je aplikovat postupně dané operace na dané dva stromy tak, aby po jejich provedení byly oba stromy shodné. Operace lze provádět v libovolném pořadí a postupně vždy aplikovat na libovolný z obou zadaných a postupně se měnících stromů. Zároveň počet těchto operací musí být nejmenší možný.

Vstup

Na vstupu jsou dva stromy, oba jsou zadány v identickém formátu. Strom je uveden řádkem s jediným celým číslem N označujícím počet uzlů ve stromu. Předpokládáme, že uzly stromu jsou očíslovány v neznámem pořadí čísly 1..N. Na dalších N−1 řádcích jsou uvedeny všechny hrany stromu, každá hrana je uvedena na jednom řádku. Hrana je specifikována dvojicí čísel A a B oddělených mezerou, kde A a B jsou čísla krajních uzlů hrany. Rodič má vždy nižší číslo než potomek. Pokud hrana vede z rodiče doleva, je uvedeno nejprve číslo potomka, pokud hrana vede z rodiče doprava je uvedeno nejprve číslo rodiče. Oba stromy na vstupu mají stejný počet uzlů.

Výstup

Na výstupu je jediné číslo P uvádějící minimální počet daných operací, které je na dané stromy nutno aplikovat tak, aby vznikly dva shodné stromy. Není rozhodující, na které uzly kterého stromu a v jakém pořadí budou operace aplikovány.

Pozor, shodné stromy nemusí mít stejná čísla uzlů na odpovídajích si místech, shodnost je vlastností pouze tvaru stromu, nepočítá s obsahem nebo číslováním jednotlivých uzlů. Uzly stromů na vstupu jsou číslovány jen proto, aby byl snadno určitelný tvar stromů.

Komentář

Úlohu lze řešit mechanickým probíráním všech možností, maximální počet uzlů ve stromu v datech je 11 (jedenáct). Odpovídající si veřejné a ostré soubory obsahují stromy se stejným počtem uzlů.

Příklad

Vstup:
6
4 2
2 5
2 1
1 3
3 6
6
2 1
1 3
4 3
3 5
6 5
Výstup:
2

Veřejná data k úloze jsou k dispozici. Veřejná data jsou uložena také v odevzdávacím systému a při každém odevzdání/spuštění úlohy dostává řešitel kompletní výstup na stdout a stderr ze svého programu pro každý soubor veřejných dat.

Veřejná data