Một tựa game mới ra đang làm bạn say mê. Trong game, bạn phải đi thu thập những bình thuốc tăng sức mạnh để đánh bại con boss ẩn "Bò thần"

Bạn đã sử dụng kĩ năng dò đường siêu hiếm và đã có được bản đồ của game dưới dạng một dãy \(N\) căn phòng (\(2 \leq N \leq 10^3\)) được đánh số từ \(1\) đến \(N\) và được kết nối bởi \(N - 1\) cạnh tạo thành một cây.

Bạn có thể sử dụng kĩ năng "bước nhảy không gian" để di chuyển giữa các phòng, trong đó mỗi bước nhảy là một lần dịch chuyển từ phòng bất kì đến phòng số 1. Sau khi hoàn thành một lần khám phá bạn sẽ dịch chuyển thẳng về phòng số 1 để tiết kiệm thời gian. Kĩ năng này tuy mạnh nhưng bị giới hạn số lần dùng, nên bạn muốn hoàn thành map và mở khóa cánh cửa đến boss sau khi dịch chuyển ít nhất có thể. Map sẽ được clear nếu bạn đi qua một căn phòng ít nhất một lần.

Cùng với đó, để nhân vật mạnh nhất có thể, bạn cần phải thu thập càng nhiều potion càng tốt. Biết mỗi lần bạn dịch chuyển, map sẽ được làm mới và một lọ potion sẽ xuất hiện ở một căn phòng ngẫu nhiên và bạn chỉ có thể lấy được nó ở lần khám phá tiếp theo, nếu không nó sẽ biến mất.

Bằng cách "ghé thăm" thư mục của game, bạn đã "tình cờ" biết được vị trí mà những potion sẽ xuất hiện trong \(N\) lần dịch chuyển tiếp theo của bạn. Hãy tính toán xem nếu bạn clear map với số lần dịch chuyển ít nhất thì sẽ thu thập được số lượng potion tối đã là bao nhiêu.

Input:

• Dòng đầu tiên chứa một số nguyên \(N\), đại diện cho số phòng có trên bản đồ.
• Dòng tiếp theo chứa \(N\) số nguyên cách nhau bởi dấu cách \(p_1, p_2, \ldots, p_N\), với \(p_i\) là phòng mà potion sẽ xuất hiện trong lần dịch chuyển thứ \(i\).
• \(N-1\) dòng tiếp theo chứa 2 số nguyên \(a\) và \(b\) (\(1 \leq a,b \leq N\)) mô tả các con đường nối giữa các phòng. Dữ liệu đảm bảo những con đường này luôn tạo thành một cây.

Output:

• Chứa một số nguyên duy nhất là số lượng potion tối đa bạn có thể lấy được sau khi clear map nhanh nhất có thể.

Scoring:

• Subtask \(1\): \(N \leq 1000\).
• Subtask \(2\): Không có ràng buộc gì thêm.

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

2