Một ngôi làng có \(n\) ngôi nhà và \(n\) con đường nối các ngôi nhà với nhau và đảm bảo các ngôi nhà liên thông với nhau.

Sắp đến mùa lễ hội nên trưởng làng muốn tổ chức nhiều lễ hội nhất có thể,một lễ hội có thể tổ chức trên một con đường và \(2\) ngôi nhà là \(2\) đầu của con đường này.Và cần đảm bảo mỗi ngôi nhà chỉ được tổ chức tối đa một lễ hội.

Hãy giúp trưởng làng tính xem có tối đa bao nhiêu lễ hội có thể tổ chức.

Đảm bảo \(2\) ngôi nhà chỉ được nối với nhau bởi tối đa một con đường.

Input

• Dòng đầu gồm một số nguyên dương \(n\) (\(3 \le n \le 5 \times 10^5\)) --- số ngôi nhà.
• \(n\) dòng tiếp theo mỗi dòng gồm \(2\) số nguyên dương \(u,v\)(\(1 \le u,v \le n\),\(u \neq v\)) --- mô tả các con đường.

Output

• Một số nguyên duy nhất là kết quả của bài toán.

Scoring

• Subtask \(1\) (\(16\%\) số điểm): mỗi ngôi nhà có tối đa \(2\) đường đi nối đến nó.
• Subtask \(2\) (\(26\%\) số điểm): \(n \le 20\).
• Subtask \(3\) (\(27\%\) số điểm): \(n \le 5 \times 10^3\).
• Subtask \(4\) (\(31\%\) số điểm): không có ràng buộc gì thêm.

Example

5
1 2
2 3
3 4
4 1
1 5

2

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

3