Giải bài trực tuyến

Bé Linh tham gia Hội thi "Bé trẻ bé trâu" do trường mầm non Chuyên Bắp Rang tổ chức. Tại đây, bé được ban tổ chức sắp xếp cho ở khách sạn miễn phí.

Ngoài bé Linh, cuộc thi này còn có sự tham gia của N sửu nhi đến từ nhiều nơi khác. Khách sạn có N + 1 phòng cho N + 1 sửu nhi ở riêng. Để chiều lòng các sửu nhi, trước ngày thi, các sửu nhi sẽ được xem ảnh của tất cả các phòng, sau đó chọn ra hai trong số N + 1 phòng mà mình thích, và ban tổ chức sẽ tìm cách sắp xếp cho các sửu nhi ở một trong hai phòng này.

Tuy nhiên, do mải mê đào mộ FB và like post của chính mình, bé Linh quên mất việc cung cấp cho ban tổ chức hai phòng mình thích. Đến ngày thi, bé Linh đã làm quen và biết được các cặp phòng mà các sửu nhi khác đã chọn. Là người dễ tính, bé Linh có thể ở bất kỳ phòng nào, vì vậy bé chỉ cần biết số cách chọn 2 phòng khác nhau sao cho ban tổ chức có thể sắp xếp được phòng cho tất cả mọi người.

Bé Linh có một chiếc laptop và nhờ bạn viết chương trình tính toán con số này. Tuy nhiên do laptop bị dán quá nhiều tranh ảnh doraemon nên hay bị nóng máy cháy bugi. Vì vậy chương trình của bạn cần chạy trong thời gian không quá 1s, bởi nếu quá thời gian này, máy có thể phát nổ và gây nguy hiểm tới tính mạng của chủ sở hữu.

Input

Dòng đầu chứa số nguyên N.

N dòng tiếp theo, dòng thứ i chứa cặp số nguyên A_i, B_i là 2 phòng mà bé thứ i đã lựa chọn. 1 ≤ A_i < B_i ≤ N + 1.

Output

Chứa một số duy nhất là đáp số bài toán.

Giới hạn

Subtask 1 (25%): N ≤ 15

Subtask 2 (35%): 16 ≤ N ≤ 50

Subtask 3 (40%): 51 ≤ N ≤ 2 * 10⁵

Ví dụ

Input 1:
2
2 3
2 3

Output 1:
2

Input 2:
3
1 2
1 2
1 2

Output 2:
0

Giải thích:

Ví dụ 1: Do 2 người 1 và 2 đều thích 2 phòng 2 và 3 nên 2 phòng này sẽ chia cho 2 người. Bé Linh chỉ có thể ở phòng 1. Vì vậy 2 cách chọn cặp phòng phù hợp cho bé là (1,2) và (1,3).

Ví dụ 2: Do có 3 người chỉ thích 2 phòng 1 và 2 nên dù bé Linh chọn phòng như thế nào, khách sạn cũng không thể xếp phòng được.