Alice đang phải tạo dữ liệu là một đồ thị dạng cây. Cô đã tạo được một cây gồm \(n\) đỉnh, các đỉnh được đánh số hiệu từ \(1\) đến \(n\). Cạnh thứ \(k\) nối hai đỉnh phân biệt có số hiệu \(u_k, v_k\) \((1 \leq u_k, v_k \leq n)\). Alice muốn tạo ra các cây mới bằng cách xóa đi ít nhất một đỉnh và xóa tất cả các cạnh kề với các đỉnh được xóa mà phần còn lại (có ít nhất một đỉnh) vẫn liên thông với nhau. Một cách xóa được gọi là đẹp nếu tập số hiệu của các đỉnh còn lại là một tập gồm các số hiệu liên tiếp nhau.

Input

• Dòng đầu chứa số nguyên dương \(n\) \((n \leq 3 \cdot 10^5)\)
• \(n-1\) dòng tiếp theo, dòng thứ \(k\) chứa hai số nguyên dương \(u_k, v_k\)

Output

• Ghi ra một dòng chứa một số là số cách xóa đẹp.

Scoring

• Subtask \(1\) (\(10\%\) số điểm): \(n \leq 100\) và đồ thị có dạng đường thẳng
• Subtask \(2\) (\(20\%\) số điểm): \(n \leq 5000\) và đồ thị có dạng đường thẳng
• Subtask \(3\) (\(20\%\) số điểm): Đồ thị có dạng đường thẳng
• Subtask \(4\) (\(20\%\) số điểm): \(n \leq 100\)
• Subtask \(5\) (\(10\%\) số điểm): \(n \leq 5000\)
• Subtask \(6\) (\(20\%\) số điểm): Không có ràng buộc gì thêm

Example

4
1 2
3 2
4 2

8

5
1 5
5 3
3 4
4 2

9