Có \(n\) thùng đựng nước sôi, các thùng nước được đánh số từ \(1\) đến \(n\), thùng nước thứ \(i\) có bán kính \(b_{i}\). Dì của Tấm lấy thêm \(n\) chiếc nắp đậy, đậy các thùng nước lại. Thùng nước thứ \(i\) được đậy bởi chiếc nắp có bán kính \(a_{i}\). Dì ghẻ bắt Tấm phải thực hiện một công việc vô lý:

• Chọn hai thùng nước bất kỳ và hoán đổi nắp của chúng cho đến khi tất cả các thùng nước đều được đậy kín (được đậy bằng nắp có bán kính to hơn hoặc bằng miệng thùng) mới cho Tấm đi hội của Vua.

Hướng dẫn Tấm xong, Dì dặn dò Cám trông chừng và theo dõi Tấm làm việc đến khi đáp ứng được yêu cầu thì ả mới để Tấm đi hội. Ngoài ra, vì thích gây khó dễ, Cám bắt buộc Tấm phải làm sao cho số thùng bị đổi nắp là ít nhất, tức là số thùng không bị đổi nắp là nhiều nhất. Chớp lấy cơ hội để làm việc tốt, trong làn sương 100 độ của nước sôi, Bụt dần hiện lên và hỏi:

"Tại sao con khóc?"

Nhưng khi Bụt vừa dứt câu thì Tấm đã giải xong bài toán, thay quần áo và đi dạo hội trong sự ngỡ ngàng của Bụt và Cám.

Câu chuyện sau đó thì ai cũng biết... Nhưng không ai hiểu được vì sao Tấm lại có thể giải bài toán hóc húa ấy một cách dễ dàng như vậy.

Thời nay, với sự tiến triển vượt bậc của công nghệ và thuật toán. Bài toán năm xưa mà Tấm giải được đã được mang ra để nghiên cứu trong kỳ thi LQDOJ CUP này.

Yêu cầu: Bạn hãy viết chương trình để giải bài toán này nhằm nghiên cứu về cách mà Tấm giải được bài toán này nhé. Khác với bài toán năm xưa, dữ liệu đầu vào có thể khác với những gì mà Dì đã cho Tấm nên có thể xảy ra trường hợp không thể đổi các nắp thùng sao cho thỏa mãn.

Input

• Dòng đầu tiên chứa số nguyên \(n\) \((1 \leq n \leq 3 \times 10^{5})\) lần lượt là số thùng nước và nắp đậy.
• Trong \(n\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(a_{i}\) và \(b_{i}\) \((1 \leq a_{i}, b_{i} \leq 10^{9})\) lần lượt là bán kính của nắp đậy và bán kính của thùng nước.

Output

• In ra \(-1\) nếu không tồn tại cách hoán đổi. Ngược lại, in ra số lượng lớn nhất có thể các thùng nước không đổi nắp.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \leq 20\).
• Subtask \(2\) (\(20\%\) số điểm): \(n \leq 1000\) và với mọi \(i,j\) \((1 \le i,j \le n)\) nào mà thoả mãn \(b_{i} \leq a_{i}, b_{j} \leq a_{j}, a_{i} \leq a_{j}\) thì cũng có \(b_{i} \geq b_{j}\) hoặc \(b_{i} < a_{j}\).
• Subtask \(3\) (\(20\%\) số điểm): \(n \leq 1000\).
• Subtask \(4\) (\(20\%\) số điểm): \(a_{i}, b_{i} \leq 100\).
• Subtask \(5\) (\(20\%\) số điểm): Không có ràng buộc gì thêm.

Example

3
2 1
3 3
5 2

3

5
1 2
2 4
4 5
6 1
5 3

1

2 2
4 4
6 5
1 1
5 3