Sở thích tiến hành các thí nghiệm vật lý năng lượng cao vào cuối tuần của Farmer John đã gây ra hậu quả ngoài ý muốn: \(N\) hố giun (\(2 \le N \le 12\), \(N\) chẵn) xuất hiện trên trang trại của ông, mỗi hố nằm tại một điểm phân biệt trên bản đồ hai chiều của trang trại.

Theo tính toán, Farmer John biết rằng các hố giun sẽ tạo thành \(N/2\) cặp liên kết. Ví dụ, nếu hố giun \(A\) và \(B\) được liên kết thành một cặp thì mọi vật thể đi vào hố giun \(A\) sẽ đi ra từ hố giun \(B\) theo cùng hướng chuyển động; tương tự, mọi vật thể đi vào hố giun \(B\) sẽ đi ra từ hố giun \(A\) theo cùng hướng. Điều này có thể dẫn đến những hậu quả khá khó chịu. Chẳng hạn, giả sử có hai hố giun được ghép cặp là \(A\) tại \((0,0)\) và \(B\) tại \((1,0)\), đồng thời cô bò Bessie bắt đầu ở vị trí \((1/2,0)\) và di chuyển theo chiều \(+x\). Bessie sẽ đi vào hố giun \(B\), đi ra từ \(A\), rồi lại đi vào \(B\), và cứ tiếp tục như vậy, khiến cô bị mắc kẹt trong một chu trình vô hạn!

Farmer John biết chính xác vị trí của từng hố giun trên trang trại. Ông biết rằng Bessie luôn đi theo chiều \(+x\), nhưng không nhớ hiện tại cô đang ở đâu. Hãy giúp Farmer John đếm số cách ghép cặp các hố giun sao cho Bessie có thể bị mắc kẹt trong một chu trình vô hạn nếu cô bắt đầu tại một vị trí không may mắn.

Dữ liệu vào

• Dòng đầu tiên chứa số hố giun \(N\).
• \(N\) dòng tiếp theo, mỗi dòng chứa hai số nguyên cách nhau bởi dấu cách, mô tả tọa độ \((x,y)\) của một hố giun.

Ràng buộc

• \(2 \le N \le 12\) và \(N\) chẵn.
• Mỗi tọa độ nằm trong đoạn từ \(0\) đến \(1\,000\,000\,000\).
• Các hố giun nằm tại những điểm đôi một phân biệt.

Dữ liệu ra

In ra số cách ghép cặp các hố giun sao cho Bessie có thể bị mắc kẹt trong một chu trình khi đi theo chiều \(+x\) từ một vị trí bắt đầu nào đó.

Ví dụ

4
0 0
1 0
1 1
0 1

2

Nguồn

USACO 2013 December Contest, Bronze — Problem 3: Wormholes

Tác giả: Brian Dean, 2013.