Dalam ilmu komputer, masalah NP-Lengkap (NP-Complete, disingkat NPC) adalah kelas masalah klasik yang menggabungkan kedalaman teoretis dan kesulitan penyelesaian—hingga saat ini belum ditemukan algoritma waktu polinomial untuk masalah-masalah tersebut, namun begitu salah satu saja dari masalah ini berhasil dipecahkan, semua masalah NP akan terselesaikan dengan mudah.

W Kecil yang antusias meneliti algoritma selalu bermimpi untuk menantang masalah NPC. Ia mengetahui bahwa "Masalah Subgraf Terinduksi Umum Maksimum" yang terkenal dalam teori graf merupakan masalah NPC klasik. Menghadapi jurang kompleksitas yang sulit dilampaui pada graf umum, W Kecil memutuskan untuk mundur selangkah dan memulai dari pohon yang memiliki struktur lebih indah untuk mempelajari masalah subgraf terhubung isomorfik pada pohon.

Secara spesifik, diberikan dua pohon tak berakar $T_1$ dan $T_2$ yang masing-masing memuat $n$ simpul, dengan simpul-simpul pada kedua pohon masing-masing diberi nomor dari $1 \sim n$. W Kecil ingin memilih suatu himpunan bagian simpul tak kosong $V_1$ di $T_1$, dan memilih suatu himpunan bagian simpul tak kosong $V_2$ di $T_2$, sambil mempertahankan semua sisi asli pada pohon asal di antara simpul-simpul di dalam masing-masing himpunan, sehingga masing-masing menginduksi dua subgraf $G_1$ dan $G_2$.

W Kecil mensyaratkan kedua subgraf terinduksi $G_1, G_2$ tersebut harus secara bersamaan memenuhi:

1. Keterhubungan: Baik $G_1$ maupun $G_2$ merupakan graf terhubung (khususnya, graf yang hanya memuat $1$ simpul juga dianggap terhubung).
2. Isomorfisme: $G_1$ dan $G_2$ saling isomorfik. Artinya, terdapat suatu bijeksi (korespondensi satu-satu) $f : V_1 \to V_2$ dari $V_1$ ke $V_2$ sedemikian sehingga untuk setiap $u, v \in V_1$, $u$ dan $v$ terhubung oleh sebuah sisi di $G_1$ jika dan hanya jika $f(u)$ dan $f(v)$ terhubung oleh sebuah sisi di $G_2$. Catatan: Simpul-simpul yang saling berkorespondensi $u$ dan $f(u)$ tidak diharuskan memiliki nomor yang sama.

Sekarang, W Kecil menyerahkan masalah yang telah disederhanakan ini kepada Anda: hitunglah berapa banyak simpul maksimum yang dapat dimuat oleh subgraf terhubung isomorfik yang memenuhi persyaratan di atas (yaitu carilah nilai maksimum dari $|V_1|$)?

Masukan

Baca data dari stdin.

Baris pertama berisi sebuah bilangan bulat positif $n$, yang menyatakan jumlah simpul pada masing-masing pohon.

Selanjutnya $n - 1$ baris berikutnya masing-masing berisi dua bilangan bulat positif $u, v$, yang menyatakan sebuah sisi tak berarah $(u, v)$ pada pohon $T_1$.

Selanjutnya $n - 1$ baris berikutnya masing-masing berisi dua bilangan bulat positif $u, v$, yang menyatakan sebuah sisi tak berarah $(u, v)$ pada pohon $T_2$.

Keluaran

Keluarkan ke stdout.

Keluarkan satu baris berisi sebuah bilangan bulat positif, yang menyatakan jumlah simpul maksimum dari subgraf terhubung isomorfik yang dipilih.

Contoh

Masukan 1

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

Keluaran 1

3

Catatan

Pilih himpunan simpul $V_1 = \{1, 2, 3\}$ di $T_1$ dan himpunan simpul $V_2 = \{1, 2, 3\}$ di $T_2$. Dengan memetakan simpul $1, 2, 3$ di $V_1$ secara berurutan ke simpul $2, 1, 3$ di $V_2$, kedua subgraf yang terinduksi sama-sama berupa rantai yang memuat $3$ simpul, sehingga memenuhi keterhubungan dan isomorfisme.

Karena $T_1$ sendiri adalah sebuah rantai, sebarang subgraf terhubungnya pasti juga berupa rantai; sedangkan rantai terpanjang pada graf bintang $T_2$ hanya memuat $3$ simpul, sehingga tidak mungkin memilih subgraf terhubung isomorfik dengan jumlah simpul lebih dari $3$.

Contoh 2

Lihat npc/npc2.in dan npc/npc2.ans di direktori peserta.

Contoh ini memenuhi batasan Subtugas $1$.

Contoh 3

Lihat npc/npc3.in dan npc/npc3.ans di direktori peserta.

Contoh ini memenuhi batasan Subtugas $4$.

Contoh 4

Lihat npc/npc4.in dan npc/npc4.ans di direktori peserta.

Contoh ini memenuhi batasan Subtugas $7$.

Subtugas

Untuk seluruh data uji, dijamin bahwa $1 \le n \le 500$, nomor kedua titik ujung dari setiap sisi berada di antara $1 \sim n$, dan kedua graf yang diberikan merupakan pohon yang valid.

Skor penuh untuk soal ini adalah $150$ poin, menggunakan penilaian terikat per subtugas. Anda hanya akan mendapatkan skor suatu subtugas jika berhasil melewati seluruh kasus uji dalam subtugas tersebut. Rincian batasan data untuk masing-masing subtugas dapat dilihat pada tabel di bawah ini.

Sifat Khusus A: Derajat setiap simpul pada kedua pohon tidak melebihi $3$.

Sifat Khusus B: Terdapat suatu solusi optimal yang pemetaan isomorfismenya memetakan simpul $1$ dari $T_1$ ke simpul $1$ dari $T_2$.

Sifat Khusus C: Dijamin bahwa jawaban akhir tidak kurang dari $n - 1$.

Catatan: Derajat suatu simpul pada pohon adalah jumlah sisi yang terhubung langsung dengan simpul tersebut.