Innen informatikk er NP-komplette (NP-Complete, forkortet NPC) problemer en klasse av klassiske problemer som kombinerer teoretisk dybde og beregningsmessig vanskelighetsgrad – hittil er det ikke funnet noen polynomisk tidsalgoritme for dem, men så snart et eneste av disse problemene blir løst, vil alle NP-problemer løses enkelt.

Lille W, som brenner for algoritmeforskning, har alltid drømt om å utfordre NPC-problemer. Han fikk vite at det berømte «problemet med største felles induserte delgraf» i grafteorien nettopp er et klassisk NPC-problem. Stilt overfor det uoverkommelige kompleksitetsgapet på generelle grafer bestemte lille W seg for å ta et skritt tilbake og starte med trær, som har en mer elegant struktur, for å studere problemet med isomorfe sammenhengende delgrafer på trær.

Mer spesifikt er det gitt to urotfestede trær $T_1$ og $T_2$ som hvert inneholder $n$ noder, der nodene i begge trærne er nummerert fra $1 \sim n$. Lille W ønsker å velge en ikke-tom delmengde av noder $V_1$ i $T_1$ og en ikke-tom delmengde av noder $V_2$ i $T_2$, samtidig som alle opprinnelige kanter i det respektive treet mellom nodene innad i hver mengde beholdes, slik at to delgrafer $G_1$ og $G_2$ induseres.

Lille W krever at de to induserte delgrafene $G_1, G_2$ samtidig oppfyller:

1. Sammenheng: Både $G_1$ og $G_2$ er sammenhengende grafer (spesielt regnes også en graf som kun inneholder $1$ node som sammenhengende).
2. Isomorfi: $G_1$ og $G_2$ er isomorfe. Det vil si at det finnes en bijeksjon (en-til-en-korrespondanse) $f : V_1 \to V_2$ fra $V_1$ til $V_2$ slik at for enhver $u, v \in V_1$ er $u$ og $v$ forbundet med en kant i $G_1$ hvis og bare hvis $f(u)$ og $f(v)$ er forbundet med en kant i $G_2$. Merk: De tilsvarende nodene $u$ og $f(u)$ trenger ikke å ha samme nodenummer.

Nå overlater lille W dette forenklede problemet til deg: beregn hvor mange noder de isomorfe sammenhengende delgrafene som oppfyller kravene ovenfor maksimalt kan inneholde (det vil si finn den maksimale verdien av $|V_1|$)?

Inndata

Les data fra stdin.

Den første linjen inneholder et positivt heltall $n$, som angir antall noder i hvert tre.

De neste $n - 1$ linjene inneholder hver to positive heltall $u, v$, som representerer en urettet kant $(u, v)$ i treet $T_1$.

De neste $n - 1$ linjene inneholder hver to positive heltall $u, v$, som representerer en urettet kant $(u, v)$ i treet $T_2$.

Utdata

Skriv utdata til stdout.

Skriv ut én linje med ett positivt heltall, som representerer det maksimale antallet noder i de valgte isomorfe sammenhengende delgrafene.

Eksempler

Inndata 1

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

Utdata 1

3

Forklaring

Velg nodemengden $V_1 = \{1, 2, 3\}$ i $T_1$ og nodemengden $V_2 = \{1, 2, 3\}$ i $T_2$. Ved å avbilde nodene $1, 2, 3$ i $V_1$ etter tur til nodene $2, 1, 3$ i $V_2$, blir begge de induserte delgrafene kjeder som inneholder $3$ noder, noe som oppfyller både sammenheng og isomorfi.

Siden $T_1$ selv er en kjede, må enhver sammenhengende delgraf av $T_1$ også være en kjede; samtidig inneholder den lengste kjeden i stjernegrafen $T_2$ bare $3$ noder, så det er umulig å velge isomorfe sammenhengende delgrafer med flere enn $3$ noder.

Eksempel 2

Se npc/npc2.in og npc/npc2.ans i deltakerens katalog.

Dette eksempelet oppfyller betingelsene i deloppgave $1$.

Eksempel 3

Se npc/npc3.in og npc/npc3.ans i deltakerens katalog.

Dette eksempelet oppfyller betingelsene i deloppgave $4$.

Eksempel 4

Se npc/npc4.in og npc/npc4.ans i deltakerens katalog.

Dette eksempelet oppfyller betingelsene i deloppgave $7$.

Deloppgaver

For alle testdata er det garantert at $1 \le n \le 500$, at numrene til begge endepunktene for hver kant ligger mellom $1 \sim n$, og at de to oppgitte grafene begge er gyldige trær.

Full poengsum for denne oppgaven er $150$ poeng, og det brukes gruppert testing per deloppgave. Du får kun poengene for en deloppgave dersom du består alle testtilfellene i den deloppgaven. Detaljerte datagrenser for hver deloppgave vises i tabellen nedenfor.

Spesiell egenskap A: Graden til alle noder i begge trærne overstiger ikke $3$.

Spesiell egenskap B: Det finnes en optimal løsning hvis isomorfiavbildning sender node $1$ i $T_1$ til node $1$ i $T_2$.

Spesiell egenskap C: Det er garantert at det endelige svaret ikke er mindre enn $n - 1$.

Merk: Graden til en node i et tre viser til antallet kanter som er direkte knyttet til denne noden.