Bạn được cho một cây nhị phân gồm \(n\) đỉnh có gốc là đỉnh \(s\) sao cho mỗi đỉnh có đúng \(0\) hoặc \(2\) đỉnh con. Bạn được phép thực hiện thao tác sau đây với số lần tuỳ ý: chọn một đỉnh có hai đỉnh con và đảo vị trí của hai cây con có gốc là hai đỉnh con đó.

Ví dụ, cho một cây nhị phân gồm \(5\) đỉnh có gốc là đỉnh \(1\), thực hiện thao tác chọn đỉnh \(1\) và đảo vị trí của cây con gốc \(2\) và cây con gốc \(3\):

Tiếp tục thực hiện thao tác chọn đỉnh \(2\) và đảo vị trí của cây con gốc \(4\) và cây con gốc \(5\):

Hãy tìm cách thực hiện thao tác sao cho số lượng cặp nghịch thế trong dãy được tạo ra từ thứ tự duyệt trước (Pre-order Traversal) của cây nhận được sau cùng là nhỏ nhất, biết rằng số lượng cặp nghịch thế của một dãy \(a_1, a_2, \ldots, a_m\) là số lượng cặp vị trí \((i, j)\) thoả mãn \(1 \leq i < j \leq m\) và \(a_i > a_j\). Ví dụ, dãy thứ tự duyệt trước của cây trạng thái \(1\) là \(\{1, 2, 4, 5, 3\}\) có \(2\) cặp nghịch thế, dãy thứ tự duyệt trước của cây trạng thái \(2\) là \(\{1, 3, 2, 4, 5\}\) có \(1\) cặp nghịch thế, dãy thứ tự duyệt trước của cây trạng thái \(3\) là \(\{1, 3, 2, 5, 4\}\) có \(2\) cặp nghịch thế.

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(s\) \((1 \leq s \leq n \leq 2 \times 10^5)\) là số lượng đỉnh của cây và đỉnh gốc của cây.
• Trong \(n-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u\) và \(v\) \((1 \leq u, v \leq n)\) mô tả một cạnh của cây.

Output

• Một số nguyên duy nhất là số cặp nghịch thế nhỏ nhất theo yêu cầu bài toán.

Scoring

• Subtask \(1\) (\(15\%\) số điểm): \(n \leq 16\).
• Subtask \(2\) (\(40\%\) số điểm): \(n \leq 5 \times 10^3\).
• Subtask \(3\) (\(25\%\) số điểm): Đỉnh cha của đỉnh \(u\) \((2 \leq u \leq n)\) là đỉnh \(\left\lfloor \frac{u}{2} \right\rfloor\).
• Subtask \(4\) (\(20\%\) số điểm): Không có ràng buộc gì thêm.

Example

Test 1

Input

5 1
1 2
5 2
2 4
3 1

Output

1

Note

Cây được biến đổi thành dạng như sau:

Dãy thứ tự duyệt trước là \(\{1, 3, 2, 4, 5\}\) có đúng \(1\) cặp nghịch thế là kết quả tối ưu.

7 3
2 4
6 7
1 6
6 3
3 4
4 5

7