Í tölvunarfræði eru NP-fullkomin (NP-Complete, skammstafað NPC) verkefni flokkur sígildra verkefna sem sameina fræðilega dýpt og þunga reikniörðugleika — enn sem komið er hefur enginn margliðutíma reiknirit fundist fyrir þau, en um leið og eitt einasta slíkt verkefni verður leyst munu öll NP-verkefni leysast auðveldlega.

Litli W, sem hefur brennandi áhuga á rannsóknum á reikniritum, hefur alltaf dreymt um að skora NPC-verkefni á hólm. Hann komst að því að hið fræga „verkefni um stærsta sameiginlega spanset (induced) hlutnet“ í netafræði er einmitt sígilt NPC-verkefni. Frammi fyrir óyfirstíganlegu flækjustigsbili á almennum netum ákvað litli W að stíga skref til baka og byrja á trjám, sem hafa mun fallegri byggingu, til að rannsaka verkefnið um einsmóta samanhangandi hlutnet á trjám.

Nánar tiltekið eru gefin tvö órætur tré $T_1$ og $T_2$ sem hvort um sig inniheldur $n$ hnúta, og eru hnútar beggja trjánna númeraðir frá $1 \sim n$. Litli W vill velja ótómt hlutmengi hnúta $V_1$ í $T_1$ og ótómt hlutmengi hnúta $V_2$ í $T_2$, og halda um leið öllum upprunalegum leggjum í viðkomandi tré milli hnútanna innan hvors mengis, þannig að tvö hlutnet $G_1$ og $G_2$ séu spanin (induced) hvort um sig.

Litli W krefst þess að hlutnetin tvö $G_1, G_2$ uppfylli samtímis:

1. Samhengi: Bæði $G_1$ og $G_2$ eru samanhangandi net (sér í lagi telst net sem inniheldur aðeins $1$ hnút einnig samanhangandi).
2. Einsmótun: $G_1$ og $G_2$ eru einsmóta. Það er að segja, til er gagntæk vörpun (einn-á-einn samsvörun) $f : V_1 \to V_2$ frá $V_1$ yfir í $V_2$ þannig að fyrir sérhver $u, v \in V_1$ eru $u$ og $v$ tengdir með legg í $G_1$ þá og því aðeins að $f(u)$ og $f(v)$ séu tengdir með legg í $G_2$. Athugið: Samsvarandi hnútar $u$ og $f(u)$ þurfa ekki að hafa sama númer.

Nú felur litli W þér þetta einfaldaða verkefni: reiknaðu hve marga hnúta einsmóta samanhangandi hlutnet sem uppfylla ofangreindar kröfur geta innihaldið að hámarki (þ.e. finndu hámarksgildi $|V_1|$)?

Inntak

Lesið gögn úr stdin.

Fyrsta línan inniheldur jákvæða heiltölu $n$, sem táknar fjölda hnúta í hvoru tré.

Næstu $n - 1$ línur innihalda hver um sig tvær jákvæðar heiltölur $u, v$, sem tákna óstefndan legg $(u, v)$ í trénu $T_1$.

Næstu $n - 1$ línur innihalda hver um sig tvær jákvæðar heiltölur $u, v$, sem tákna óstefndan legg $(u, v)$ í trénu $T_2$.

Úttak

Skrifið úttak í stdout.

Prentið eina línu með einni jákvæðri heiltölu, sem táknar hámarksfjölda hnúta í völdum einsmóta samanhangandi hlutnetum.

Dæmi

Inntak 1

4
1 2
2 3
3 4
1 2
1 3
1 4

Úttak 1

3

Skýring

Veljum hnútamengið $V_1 = \{1, 2, 3\}$ í $T_1$ og hnútamengið $V_2 = \{1, 2, 3\}$ í $T_2$. Ef hnútunum $1, 2, 3$ í $V_1$ er varpað í röð á hnútana $2, 1, 3$ í $V_2$, þá eru bæði hlutnetin keðjur sem innihalda $3$ hnúta, og uppfylla því bæði samhengi og einsmótun.

Þar sem $T_1$ er sjálft keðja hlýtur sérhvert samanhangandi hlutnet þess einnig að vera keðja; hins vegar inniheldur lengsta keðjan í stjörnunetinu $T_2$ aðeins $3$ hnúta, svo ómögulegt er að velja einsmóta samanhangandi hlutnet með fleiri en $3$ hnútum.

Dæmi 2

Sjá npc/npc2.in og npc/npc2.ans í möppu keppanda.

Þetta dæmi uppfyllir skorður undirverkefnis $1$.

Dæmi 3

Sjá npc/npc3.in og npc/npc3.ans í möppu keppanda.

Þetta dæmi uppfyllir skorður undirverkefnis $4$.

Dæmi 4

Sjá npc/npc4.in og npc/npc4.ans í möppu keppanda.

Þetta dæmi uppfyllir skorður undirverkefnis $7$.

Undirverkefni

Fyrir öll prófunargögn er tryggt að $1 \le n \le 500$, númer beggja endapunkta hvers leggs eru á bilinu $1 \sim n$, og bæði gefnu netin eru gild tré.

Fullt stigafjöldi þessa verkefnis er $150$ stig og notast er við knippaðar prófanir í undirverkefnum. Þú færð aðeins stig fyrir undirverkefni ef þú stenst öll prófunartilvik í því undirverkefni. Nákvæmar gagnaskorður hvers undirverkefnis má sjá í töflunni hér að neðan.

Sérstakur eiginleiki A: Stig allra hnúta í báðum trjánum er í mesta lagi $3$.

Sérstakur eiginleiki B: Til er besta lausn þar sem einsmótunarvörpunin varpar hnúti $1$ í $T_1$ á hnút $1$ í $T_2$.

Sérstakur eiginleiki C: Tryggt er að lokasvarið sé ekki minna en $n - 1$.

Athugasemd: Stig hnúts í tré vísar til fjölda leggja sem tengjast þeim hnúti beint.