Tietojenkäsittelytieteessä NP-täydelliset (NP-Complete, lyhyesti NPC) ongelmat ovat klassisten ongelmien luokka, jossa yhdistyvät teoreettinen syvyys ja ratkaisemisen vaikeus — niille ei ole toistaiseksi löydetty polynomiaikaista algoritmia, mutta heti kun yksikin näistä ongelmista ratkaistaan, kaikki NP-ongelmat ratkeavat samalla.

Algoritmitutkimukseen intohimoisesti suhtautuva pikku W on aina haaveillut NPC-ongelmien haastamisesta. Hän sai tietää, että graafiteorian kuuluisa ”suurimman yhteisen indusoidun aligraafin ongelma” on juuri klassinen NPC-ongelma. Kohdattuaan yleisten graafien ylittämättömän aikavaativuuskuilun pikku W päätti ottaa askeleen taaksepäin ja aloittaa rakenteeltaan kauniimmista puista tutkiakseen puiden isomorfisten yhtenäisten aligraafien ongelmaa.

Tarkemmin sanottuna annetaan kaksi juuretonta puuta $T_1$ ja $T_2$, joista kumpikin sisältää $n$ solmua, ja molempien puiden solmut on numeroitu väliltä $1 \sim n$. Pikku W haluaa valita epätyhjän solmujen osajoukon $V_1$ puusta $T_1$ ja epätyhjän solmujen osajoukon $V_2$ puusta $T_2$ säilyttäen kaikki alkuperäisen puun kaaret kummankin joukon sisäisten solmujen välillä, jolloin saadaan indusoitua kaksi aligraafia $G_1$ ja $G_2$.

Pikku W vaatii, että indusoidut aligraafit $G_1, G_2$ täyttävät samanaikaisesti seuraavat ehdot:

1. Yhtenäisyys: Sekä $G_1$ että $G_2$ ovat yhtenäisiä graafeja (erityisesti myös vain $1$ solmun sisältävä graafi katsotaan yhtenäiseksi).
2. Isomorfisuus: $G_1$ ja $G_2$ ovat isomorfiset. Toisin sanoen on olemassa bijektio (yksi yhteen -vastaavuus) $f : V_1 \to V_2$ joukosta $V_1$ joukkoon $V_2$ siten, että kaikilla $u, v \in V_1$ solmujen $u$ ja $v$ välillä on kaari graafissa $G_1$ jos ja vain jos solmujen $f(u)$ ja $f(v)$ välillä on kaari graafissa $G_2$. Huomautus: toisiaan vastaavien solmujen $u$ ja $f(u)$ numeroiden ei tarvitse olla samat.

Nyt pikku W antaa tämän yksinkertaistetun ongelman sinulle: laske, kuinka monta solmua yllä olevat vaatimukset täyttävät isomorfiset yhtenäiset aligraafit voivat enintään sisältää (eli etsi suurin mahdollinen arvo merkinnälle $|V_1|$)?

Syöte

Lue syöte standardisyötteestä stdin.

Ensimmäisellä rivillä on positiivinen kokonaisluku $n$, joka ilmoittaa solmujen lukumäärän kummassakin puussa.

Seuraavat $n - 1$ riviä sisältävät kukin kaksi positiivista kokonaislukua $u, v$, jotka kuvaavat suuntaamatonta kaarta $(u, v)$ puussa $T_1$.

Seuraavat $n - 1$ riviä sisältävät kukin kaksi positiivista kokonaislukua $u, v$, jotka kuvaavat suuntaamatonta kaarta $(u, v)$ puussa $T_2$.

Tuloste

Kirjoita tuloste standarditulosteeseen stdout.

Tulosta yhdelle riville yksi positiivinen kokonaisluku, joka ilmaisee valittujen isomorfisten yhtenäisten aligraafien suurimman mahdollisen solmujen määrän.

Esimerkit

Syöte 1

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

Tuloste 1

3

Selitys

Valitaan puusta $T_1$ solmujoukko $V_1 = \{1, 2, 3\}$ ja puusta $T_2$ solmujoukko $V_2 = \{1, 2, 3\}$. Kun joukon $V_1$ solmut $1, 2, 3$ asetetaan järjestyksessä vastaamaan joukon $V_2$ solmuja $2, 1, 3$, molemmat indusoidut aligraafit ovat $3$ solmun ketjuja, joten ne ovat sekä yhtenäisiä että keskenään isomorfisia.

Koska $T_1$ on itse ketju, jokainen sen yhtenäinen aligraafi on myös välttämättä ketju; toisaalta tähtigraafin $T_2$ pisin ketju sisältää vain $3$ solmua, joten yli $3$ solmun kokoisia isomorfisia yhtenäisiä aligraafeja ei ole mahdollista valita.

Esimerkki 2

Katso tiedostot npc/npc2.in ja npc/npc2.ans kilpailijan hakemistosta.

Tämä esimerkki täyttää osatehtävän $1$ rajoitteet.

Esimerkki 3

Katso tiedostot npc/npc3.in ja npc/npc3.ans kilpailijan hakemistosta.

Tämä esimerkki täyttää osatehtävän $4$ rajoitteet.

Esimerkki 4

Katso tiedostot npc/npc4.in ja npc/npc4.ans kilpailijan hakemistosta.

Tämä esimerkki täyttää osatehtävän $7$ rajoitteet.

Osatehtävät

Kaikissa testitapauksissa taataan, että $1 \le n \le 500$, jokaisen kaaren molempien päätepisteiden numerot ovat välillä $1 \sim n$, ja molemmat annetut graafit ovat kelvollisia puita.

Tämän tehtävän maksimipistemäärä on $150$ pistettä, ja tehtävässä käytetään osatehtäväkohtaista arvostelua. Saat osatehtävän pisteet vain, jos ohjelmasi läpäisee kaikki kyseisen osatehtävän testitapaukset. Kunkin osatehtävän tarkat rajoitteet on esitetty alla olevassa taulukossa.

Erityisominaisuus A: Kummankin puun kaikkien solmujen aste on enintään $3$.

Erityisominaisuus B: On olemassa optimaalinen ratkaisu, jonka isomorfismikuvaus kuvaa puun $T_1$ solmun $1$ puun $T_2$ solmuksi $1$.

Erityisominaisuus C: Taataan, että lopullinen vastaus on vähintään $n - 1$.

Huomautus: Puun solmun aste tarkoittaa kyseiseen solmuun suoraan liittyvien kaarien lukumäärää.