Đất nước Byteland có \(n\) thành phố được đánh số từ \(1\) đến \(n\). Các thành phố này được kết nối với nhau bởi \(n + 1\) con đường hai chiều. Hệ thống đường hai chiều được xây dựng để đảm bảo rằng từ một thành phố bất kỳ ta có thể di chuyển trực tiếp hoặc gián tiếp đến mọi thành phố còn lại, và không tồn tại cặp thành phố nào được kết nối trực tiếp bởi hai (trở lên) con đường khác nhau.

Nhàn và Nhi là một cặp doanh nhân rất nhiệt huyết và hào phóng. Mỗi người đều muốn thuê trọn một con đường để tổ chức lễ hội ẩm thực đường phố cho người dân Byteland. Hai con đường được thuê đều sẽ bị phong tỏa và xe cộ không thể di chuyển qua lại. Nhà chức trách Byteland liền nhờ Lương lập trình tính số phương án cho thuê khác nhau để \(n\) thành phố tiếp tục liên thông với nhau. Nói cách khác, hãy đếm số cặp đường đi hai chiều khác nhau để khi bỏ chúng ra thì từ một thành phố bất kỳ ta vẫn có thể di chuyển đến mọi thành phố còn lại. Lương đang rất bận bịu với học kỳ mới nên các bạn hãy giúp anh ấy nhé!

Input

• Dòng đầu tiên gồm số nguyên dương \(n\) (\(4 \leq n \leq 10^5\))
• \(n + 1\) dòng tiếp theo, mỗi dòng gồm 2 số nguyên dương \(u, v\) thể hiện đường đi 2 chiều từ thành phố \(u\) tới \(v\) (\(1 \leq u, v \leq n, u \neq v\))

Output

• In ra số nguyên duy nhất là số lượng phương án thỏa mãn

Scoring

• Subtask 1: \(\ n \leq 100\)
• Subtask 2: \(\ n \leq 5000\)
• Subtask 3: \(\ n \leq 10^5\)

Example

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

8