In der Informatik sind NP-vollständige (NP-Complete, kurz NPC) Probleme eine Klasse klassischer Probleme, die theoretische Tiefe und Lösungsschwierigkeit vereinen – bisher wurde für sie noch kein Algorithmus mit polynomieller Laufzeit gefunden, doch sobald auch nur eines dieser Probleme gelöst wird, lassen sich alle NP-Probleme mühelos lösen.

Der von der Algorithmenforschung begeisterte kleine W träumt schon lange davon, NPC-Probleme herauszufordern. Er hat erfahren, dass das berühmte „Problem des maximalen gemeinsamen induzierten Teilgraphen“ in der Graphentheorie genau ein klassisches NPC-Problem ist. Angesichts der unüberwindbaren Komplexitätskluft bei allgemeinen Graphen beschloss der kleine W, einen Schritt zurückzutreten und zunächst mit den strukturell eleganteren Bäumen zu beginnen, um das Problem isomorpher zusammenhängender Teilgraphen auf Bäumen zu untersuchen.

Konkret sind zwei unbewurzelte Bäume $T_1$ und $T_2$ gegeben, die jeweils $n$ Knoten enthalten, wobei die Knoten beider Bäume jeweils von $1 \sim n$ nummeriert sind. Der kleine W möchte in $T_1$ eine nichtleere Knotenteilmenge $V_1$ und in $T_2$ eine nichtleere Knotenteilmenge $V_2$ auswählen und dabei alle ursprünglichen Kanten des jeweiligen Baumes zwischen den Knoten innerhalb jeder Menge beibehalten, sodass jeweils zwei Teilgraphen $G_1$ und $G_2$ induziert werden.

Der kleine W verlangt, dass die beiden induzierten Teilgraphen $G_1, G_2$ gleichzeitig Folgendes erfüllen:

1. Zusammenhang: Sowohl $G_1$ als auch $G_2$ sind zusammenhängende Graphen (insbesondere gilt auch ein Graph, der nur $1$ Knoten enthält, als zusammenhängend).
2. Isomorphie: $G_1$ und $G_2$ sind isomorph. Das heißt, es existiert eine Bijektion (eineindeutige Zuordnung) $f : V_1 \to V_2$ von $V_1$ nach $V_2$, sodass für beliebige $u, v \in V_1$ die Knoten $u$ und $v$ genau dann in $G_1$ durch eine Kante verbunden sind, wenn $f(u)$ und $f(v)$ in $G_2$ durch eine Kante verbunden sind. Hinweis: Die einander zugeordneten Knoten $u$ und $f(u)$ müssen nicht dieselbe Nummer haben.

Nun übergibt der kleine W dieses vereinfachte Problem an dich: Bitte berechne, wie viele Knoten die isomorphen zusammenhängenden Teilgraphen, die die obigen Anforderungen erfüllen, höchstens enthalten können (d. h. bestimme das Maximum von $|V_1|$).

Eingabe

Lies die Daten von stdin ein.

Die erste Zeile enthält eine positive ganze Zahl $n$, die die Anzahl der Knoten in jedem Baum angibt.

Die nächsten $n - 1$ Zeilen enthalten jeweils zwei positive ganze Zahlen $u, v$, die eine ungerichtete Kante $(u, v)$ im Baum $T_1$ darstellen.

Die nächsten $n - 1$ Zeilen enthalten jeweils zwei positive ganze Zahlen $u, v$, die eine ungerichtete Kante $(u, v)$ im Baum $T_2$ darstellen.

Ausgabe

Gib das Ergebnis auf stdout aus.

Gib eine Zeile mit einer positiven ganzen Zahl aus, die die maximale Knotenanzahl der ausgewählten isomorphen zusammenhängenden Teilgraphen angibt.

Beispiele

Eingabe 1

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

Ausgabe 1

3

Hinweis

Wählt man in $T_1$ die Knotenmenge $V_1 = \{1, 2, 3\}$ und in $T_2$ die Knotenmenge $V_2 = \{1, 2, 3\}$ und ordnet die Knoten $1, 2, 3$ aus $V_1$ der Reihe nach den Knoten $2, 1, 3$ aus $V_2$ zu, so sind beide induzierten Teilgraphen Ketten mit $3$ Knoten und erfüllen sowohl den Zusammenhang als auch die Isomorphie.

Da $T_1$ selbst eine Kette ist, muss auch jeder zusammenhängende Teilgraph davon eine Kette sein; im Sterngraphen $T_2$ enthält die längste Kette jedoch nur $3$ Knoten, weshalb keine isomorphen zusammenhängenden Teilgraphen mit mehr als $3$ Knoten ausgewählt werden können.

Beispiel 2

Siehe npc/npc2.in und npc/npc2.ans im Teilnehmerverzeichnis.

Dieses Beispiel erfüllt die Bedingungen von Teilaufgabe $1$.

Beispiel 3

Siehe npc/npc3.in und npc/npc3.ans im Teilnehmerverzeichnis.

Dieses Beispiel erfüllt die Bedingungen von Teilaufgabe $4$.

Beispiel 4

Siehe npc/npc4.in und npc/npc4.ans im Teilnehmerverzeichnis.

Dieses Beispiel erfüllt die Bedingungen von Teilaufgabe $7$.

Teilaufgaben

Für alle Testdaten ist garantiert, dass $1 \le n \le 500$ gilt, die Nummern beider Endpunkte jeder Kante zwischen $1 \sim n$ liegen und die beiden gegebenen Graphen gültige Bäume sind.

Die Gesamtpunktzahl dieser Aufgabe beträgt $150$ Punkte, und es wird gebündeltes Testen nach Teilaufgaben verwendet. Du erhältst die Punkte einer Teilaufgabe nur dann, wenn du alle Testfälle in dieser Teilaufgabe bestehst. Die genauen Datenbereiche der einzelnen Teilaufgaben sind in der folgenden Tabelle aufgeführt.

Besondere Eigenschaft A: Der Grad aller Knoten in beiden Bäumen beträgt höchstens $3$.

Besondere Eigenschaft B: Es existiert eine optimale Lösung, deren Isomorphieabbildung den Knoten $1$ von $T_1$ auf den Knoten $1$ von $T_2$ abbildet.

Besondere Eigenschaft C: Es ist garantiert, dass die endgültige Antwort nicht kleiner als $n - 1$ ist.

Anmerkung: Der Grad eines Knotens in einem Baum bezeichnet die Anzahl der Kanten, die direkt mit diesem Knoten verbunden sind.