Optimal Station Frequencies

Một kỹ sư đang thiết lập một mạng lưới truyền dẫn gồm $n$ trạm phát tín hiệu được đánh số từ $1$ đến $n$. Các trạm được kết nối với nhau theo cấu trúc một cây gồm $n - 1$ đường truyền hai chiều.

Tại mỗi trạm phát $v$, kỹ sư cần gán một tần số hoạt động là số nguyên $a_v$ thỏa mãn điều kiện $l_v ≤ a_v ≤ r_v$, trong đó $l_v$ và $r_v$ là hai biên tần số cho phép đã được xác định trước của trạm đó.

Để kiểm tra độ ổn định cũng như hạn chế sự can thiệp sóng giữa các trạm lân cận, kỹ sư muốn tối đa hóa tổng độ chênh lệch tần số trên toàn bộ mạng lưới. Độ tương phản của mạng lưới được định nghĩa là tổng giá trị $|a_u - a_v|$ trên tất cả các đường truyền nối giữa hai trạm $u$ và $v$.

Hãy giúp kỹ sư tìm giá trị độ tương phản lớn nhất có thể đạt được cho mạng lưới.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên $t$ ($1 ≤ t ≤ 250$), biểu thị số lượng bộ test. Các dòng tiếp theo mô tả chi tiết từng bộ test.

Dòng đầu tiên của mỗi bộ test chứa số nguyên $n$ ($2 ≤ n ≤ 10^5$), biểu thị số lượng trạm phát trong mạng lưới. Tổng giá trị của $n$ trên tất cả các bộ test không vượt quá $2 · 10^5$ ($\sum n ≤ 2 · 10^5$).

Dòng thứ $i$ trong số $n$ dòng tiếp theo chứa hai số nguyên $l_i$ và $r_i$ ($1 ≤ l_i ≤ r_i ≤ 10^9$), xác định khoảng tần số cho phép của trạm thứ $i$.

Mỗi dòng trong số $n - 1$ dòng tiếp theo chứa hai số nguyên $u$ và $v$ ($1 ≤ u, v ≤ n, u ≠ v$), cho biết có một đường truyền kết nối trực tiếp giữa trạm $u$ và trạm $v$.

Dữ liệu đảm bảo đồ thị gồm các trạm và đường truyền luôn là một cây.

Kết quả

Với mỗi bộ test, in ra một số nguyên duy nhất là độ tương phản lớn nhất có thể đạt được của mạng lưới.

Chấm điểm

Subtask 1 (30 points). $n ≤ 18$

Subtask 2 (70 points). $1 ≤ t ≤ 250$; $2 ≤ n ≤ 10^5$; $\sum n ≤ 2 · 10^5$

Ví dụ

Input

3
2
1 6
3 8
1 2
3
1 3
4 6
7 9
1 2
2 3
6
3 14
12 20
12 19
2 12
10 17
3 17
3 2
6 5
1 5
2 6
4 6

Output

7
8
62

Ghi chú

Trong bộ test thứ nhất, một cách gán tần số tối ưu là $a = {1, 8}$, mang lại độ tương phản là $|1 - 8| = 7$.

Trong bộ test thứ hai, một cách gán tần số tối ưu là $a = {1, 5, 9}$, mang lại độ tương phản là $|1 - 5| + |5 - 9| = 4 + 4 = 8$.