BÀI 3

Xem PDF

Điểm: 1800 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Peter có \(1\) bộ bài gồm \(n\) lá, với các lá được đánh số từ \(1\) đến \(n\), lá thứ \(i\) có mặt trên là giá trị \(a_i\) và mặt dưới là giá trị \(b_i\). Bạn hãy giúp Peter lật hoặc úp các lá bài sao cho số lượng giá trị khác nhau hiện lên ở trên là nhiều nhất có thể biết rằng bạn có thể lật hoặc úp vô số lần.

Input

  • Dòng đầu tiên ghi số \(n\) \((1 \le n \le 10^5)\);
  • \(n\) dòng tiếp theo, dòng thứ \(i\) chứa \(2\) số \(a_i\)\(b_i\) \((1 \le a_i, b_i \le n)\)

Output

  • Gồm \(1\) số nguyên dương là kết quả bài toán.

Example

Test 1

Input
4
1 2
1 3
4 2
2 3
Output
4
Note
  • Đây là một cách để thu được nhiều lá bài có giá trị khác nhau nhất:
    • Lật lá bài đầu tiên lên mặt trên ta thu được số \(1\).
    • Úp lá bài thứ hai xuống mặt dưới ta thu được số \(3\).
    • Lật lá bài thứ ba lên mặt trên ta thu được số \(4\).
    • Lật lá bài thứ tư lên mặt trên ta thu được số \(2\).
  • Bạn có thể làm cách khác cũng được miễn cách đó thỏa mãn là nhiều nhất.

Bình luận

Không có bình luận nào.