Trong khoa học máy tính, bài toán NP-Đầy đủ (NP-Complete, viết tắt là NPC) là một lớp các bài toán kinh điển vừa có chiều sâu lý thuyết vừa có độ khó giải quyết cao — hiện tại vẫn chưa tìm ra thuật toán thời gian đa thức cho chúng, nhưng một khi bất kỳ bài toán nào trong số đó được chinh phục, mọi bài toán NP đều sẽ được giải quyết dễ dàng.

Đam mê nghiên cứu thuật toán, Tiểu W luôn mơ ước được thách thức các bài toán NPC. Cậu biết rằng "Bài toán đồ thị con cảm sinh chung lớn nhất" nổi tiếng trong lý thuyết đồ thị chính là một bài toán NPC kinh điển. Đối mặt với khoảng cách độ phức tạp khó lòng vượt qua trên đồ thị tổng quát, Tiểu W quyết định lùi một bước, bắt đầu từ cấu trúc đẹp đẽ hơn là cây để nghiên cứu bài toán đồ thị con liên thông đẳng cấu trên cây.

Cụ thể, cho hai cây không gốc $T_1$ và $T_2$ đều gồm $n$ đỉnh, các đỉnh của cả hai cây đều được đánh số lần lượt từ $1 \sim n$. Tiểu W muốn chọn một tập con đỉnh khác rỗng $V_1$ trong $T_1$, và chọn một tập con đỉnh khác rỗng $V_2$ trong $T_2$, đồng thời giữ lại tất cả các cạnh ban đầu trong cây gốc giữa các đỉnh thuộc mỗi tập hợp để lần lượt cảm sinh ra hai đồ thị con $G_1$ và $G_2$.

Tiểu W yêu cầu hai đồ thị con cảm sinh $G_1, G_2$ phải đồng thời thỏa mãn:

1. Tính liên thông: $G_1$ và $G_2$ đều là đồ thị liên thông (đặc biệt, đồ thị chỉ chứa $1$ đỉnh cũng được coi là liên thông).
2. Tính đẳng cấu: $G_1$ và $G_2$ đẳng cấu với nhau. Tức là tồn tại một song ánh (tương ứng một-một) $f : V_1 \to V_2$ từ $V_1$ sang $V_2$, sao cho với mọi $u, v \in V_1$, $u$ và $v$ có cạnh nối trong $G_1$ khi và chỉ khi $f(u)$ và $f(v)$ có cạnh nối trong $G_2$. Lưu ý: Các đỉnh tương ứng $u$ và $f(u)$ không nhất thiết phải có cùng số hiệu.

Bây giờ, Tiểu W giao lại bài toán đã được đơn giản hóa này cho bạn: hãy tính xem đồ thị con liên thông đẳng cấu thỏa mãn các yêu cầu trên có thể chứa tối đa bao nhiêu đỉnh (tức là tìm giá trị lớn nhất của $|V_1|$)?

Dữ liệu vào

Đọc dữ liệu từ stdin.

Dòng đầu tiên chứa một số nguyên dương $n$, biểu thị số lượng đỉnh của mỗi cây.

$n - 1$ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương $u, v$, biểu thị một cạnh vô hướng $(u, v)$ trong cây $T_1$.

$n - 1$ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương $u, v$, biểu thị một cạnh vô hướng $(u, v)$ trong cây $T_2$.

Dữ liệu ra

Ghi kết quả ra stdout.

In ra một dòng gồm một số nguyên dương, biểu thị số lượng đỉnh tối đa của đồ thị con liên thông đẳng cấu được chọn.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

3

Ghi chú

Chọn tập hợp đỉnh $V_1 = \{1, 2, 3\}$ trong $T_1$ và tập hợp đỉnh $V_2 = \{1, 2, 3\}$ trong $T_2$. Cho các đỉnh $1, 2, 3$ trong $V_1$ lần lượt tương ứng với các đỉnh $2, 1, 3$ trong $V_2$, hai đồ thị con cảm sinh đều là đường đi gồm $3$ đỉnh, thỏa mãn tính liên thông và đẳng cấu.

Do bản thân $T_1$ là một đường đi nên mọi đồ thị con liên thông của nó cũng bắt buộc phải là một đường đi; trong khi đó đường đi dài nhất trong đồ thị hình sao $T_2$ chỉ chứa $3$ đỉnh, vì vậy không thể chọn được đồ thị con liên thông đẳng cấu có số đỉnh vượt quá $3$.

Ví dụ 2

Xem npc/npc2.in và npc/npc2.ans trong thư mục thí sinh.

Ví dụ này thỏa mãn điều kiện ràng buộc của nhiệm vụ con $1$.

Ví dụ 3

Xem npc/npc3.in và npc/npc3.ans trong thư mục thí sinh.

Ví dụ này thỏa mãn điều kiện ràng buộc của nhiệm vụ con $4$.

Ví dụ 4

Xem npc/npc4.in và npc/npc4.ans trong thư mục thí sinh.

Ví dụ này thỏa mãn điều kiện ràng buộc của nhiệm vụ con $7$.

Nhiệm vụ con

Đối với toàn bộ dữ liệu, đảm bảo $1 \le n \le 500$, số hiệu hai đầu mút của mỗi cạnh đều nằm trong khoảng $1 \sim n$, và hai đồ thị đã cho đều là cây hợp lệ.

Điểm tối đa của bài toán này là $150$ điểm, áp dụng chấm theo gói nhiệm vụ con. Chỉ khi vượt qua toàn bộ các test trong một nhiệm vụ con thì mới nhận được điểm của nhiệm vụ con đó. Phạm vi dữ liệu chi tiết của từng nhiệm vụ con được cho trong bảng dưới đây.

Tính chất đặc biệt A: Bậc của tất cả các đỉnh trong cả hai cây đều không vượt quá $3$.

Tính chất đặc biệt B: Tồn tại một phương án tối ưu mà ánh xạ đẳng cấu của nó cho đỉnh $1$ của $T_1$ tương ứng với đỉnh $1$ của $T_2$.

Tính chất đặc biệt C: Đảm bảo kết quả cuối cùng không nhỏ hơn $n - 1$.

Lưu ý: Bậc của một đỉnh trong cây là số lượng cạnh nối trực tiếp với đỉnh đó.