Inom datavetenskapen är NP-fullständiga (NP-Complete, förkortat NPC) problem en klass av klassiska problem som förenar teoretiskt djup med beräkningsmässig svårighetsgrad – hittills har ingen algoritm med polynomiell tid hittats för dem, men så snart något enda av dessa problem besegras kommer alla NP-problem att få sin lösning.

Lille W, som brinner för algoritmforskning, har alltid drömt om att utmana NPC-problem. Han fick veta att det berömda ”problemet med största gemensamma inducerade delgraf” inom grafteorin är just ett klassiskt NPC-problem. Inför den oöverstigliga komplexitetsklyftan på allmänna grafer bestämde sig lille W för att ta ett steg tillbaka och börja med träd, som har en mer elegant struktur, för att studera problemet med isomorfa sammanhängande delgrafer på träd.

Mer specifikt ges två orotade träd $T_1$ och $T_2$ som vart och ett innehåller $n$ noder, där noderna i båda träden är numrerade från $1 \sim n$. Lille W vill välja en icke-tom delmängd av noder $V_1$ i $T_1$ och en icke-tom delmängd av noder $V_2$ i $T_2$, samtidigt som alla ursprungliga kanter i respektive ursprungsträd mellan noderna inom varje mängd behålls, så att två delgrafer $G_1$ respektive $G_2$ induceras.

Lille W kräver att de två inducerade delgraferna $G_1, G_2$ samtidigt uppfyller:

1. Sammanhang: Både $G_1$ och $G_2$ är sammanhängande grafer (i synnerhet betraktas även en graf som endast innehåller $1$ nod som sammanhängande).
2. Isomorfi: $G_1$ och $G_2$ är isomorfa. Det vill säga, det existerar en bijektion (en-till-en-korrespondens) $f : V_1 \to V_2$ från $V_1$ till $V_2$ sådan att för alla $u, v \in V_1$ är $u$ och $v$ förbundna med en kant i $G_1$ om och endast om $f(u)$ och $f(v)$ är förbundna med en kant i $G_2$. Observera: De motsvarande noderna $u$ och $f(u)$ behöver inte ha samma nodnummer.

Nu överlämnar lille W detta förenklade problem till dig: beräkna hur många noder de isomorfa sammanhängande delgraferna som uppfyller ovanstående krav som mest kan innehålla (det vill säga bestäm det maximala värdet på $|V_1|$)?

Indata

Läs indata från stdin.

Den första raden innehåller ett positivt heltal $n$, som anger antalet noder i varje träd.

De följande $n - 1$ raderna innehåller var och en två positiva heltal $u, v$, som representerar en oriktad kant $(u, v)$ i trädet $T_1$.

De följande $n - 1$ raderna innehåller var och en två positiva heltal $u, v$, som representerar en oriktad kant $(u, v)$ i trädet $T_2$.

Utdata

Skriv utdata till stdout.

Skriv ut en rad med ett positivt heltal, som anger det maximala antalet noder i de valda isomorfa sammanhängande delgraferna.

Exempel

Indata 1

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

Utdata 1

3

Förklaring

Välj nodmängden $V_1 = \{1, 2, 3\}$ i $T_1$ och nodmängden $V_2 = \{1, 2, 3\}$ i $T_2$. Om noderna $1, 2, 3$ i $V_1$ i tur och ordning avbildas på noderna $2, 1, 3$ i $V_2$, blir båda de inducerade delgraferna kedjor med $3$ noder, vilket uppfyller både sammanhang och isomorfi.

Eftersom $T_1$ i sig är en kedja måste varje sammanhängande delgraf av $T_1$ också vara en kedja; samtidigt innehåller den längsta kedjan i stjärngrafen $T_2$ endast $3$ noder, varför det är omöjligt att välja isomorfa sammanhängande delgrafer med fler än $3$ noder.

Exempel 2

Se npc/npc2.in och npc/npc2.ans i tävlingsdeltagarens katalog.

Detta exempel uppfyller begränsningarna för deluppgift $1$.

Exempel 3

Se npc/npc3.in och npc/npc3.ans i tävlingsdeltagarens katalog.

Detta exempel uppfyller begränsningarna för deluppgift $4$.

Exempel 4

Se npc/npc4.in och npc/npc4.ans i tävlingsdeltagarens katalog.

Detta exempel uppfyller begränsningarna för deluppgift $7$.

Deluppgifter

För all testdata garanteras att $1 \le n \le 500$, att numren på båda ändpunkterna för varje kant ligger mellan $1 \sim n$, samt att de två givna graferna båda är giltiga träd.

Maxpoängen för detta problem är $150$ poäng, och grupperad testning per deluppgift tillämpas. Du får poängen för en deluppgift endast om du klarar alla testfall i den deluppgiften. Detaljerade begränsningar för varje deluppgift visas i tabellen nedan.

Särskild egenskap A: Graden för alla noder i båda träden överstiger inte $3$.

Särskild egenskap B: Det finns en optimal lösning vars isomorfiavbildning avbildar nod $1$ i $T_1$ på nod $1$ i $T_2$.

Särskild egenskap C: Det garanteras att det slutliga svaret inte är mindre än $n - 1$.

Obs: Graden för en nod i ett träd avser antalet kanter som är direkt anslutna till den noden.