Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

VOROOM - Xếp phòng

 

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 khác đến từ nhiều quốc gia 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ẽ cho các sửu nhi ở một trong hai phòng này.
Tuy nhiên, do mải mê đào mộ FB của chính mình, bé Linh quên mất việc cung cấp cho ban tổ chức 2 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é Linh 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ó 1 chiếc laptop và nhờ bạn viết một chương trình tính con số này. Tuy nhiên, do laptop bị dán quá nhiều tranh ảnh doraemon nên thường xuyên bị nóng máy cháy bugi. Vì vậy, nếu chương trình của bạn chạy quá 1s máy có thể phát 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 Ai, Bi là 2 phòng mà bé thứ i đã lựa chọn. 1 ≤ Ai < Bi ≤ 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 * 105

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)(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.


Được gửi lên bởi:VOJ Team
Ngày:2015-12-25
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: GOSU PERL6 PYPY RUST SED
Nguồn bài:VNOI Online 2016

hide comments
2016-08-31 13:38:18
AC r đọc giải của VNOI vẫn k hiểu j zZ
2016-02-01 08:47:43
THAM KHAO : http://codevnspoj.blogspot.com/
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.