ორი ტელევიზორი



პოლიკარპს ძალიან უყვარს ტელევიზორის ყურება.

მან ჩამოწერა ყველა ის გადაცემა, რომელიც მას დღეს აინტერესებს. მისი სია შეიცავს n გადაცემას, რომელთაგან i-რი გადაცემა იწყება li დროს და მთავრდება ri დროს.

პოლიკარპს აქვს ორი ტელევიზორი. მას შეუძლია უყუროს მხოლოდ ორ გადაცემას პარალელურად ორ ტელევიზორში, რადგან მოცემულ კონკრეტულ მომენტში ერთ ტელევიზორში მხოლოდ ერთი გადაცემის ყურება შეუძლია. თუ ერთი გადაცემა მთავრდება ზუსტად იმ დროს, როცა მეორე იწყება, პოლიკარპს არ შეუძლია ასეთ ორ გადაცემას ერთი და იმავე ტელევიზორში უყუროს.

პოლიკარპს სურს გაიგოს, შეუძლია თუ არა ნახოს ყველა გადაცემა და საკმარისია თუ არა ორი ტელევიზორი ამისთვის.

 

შემომავალი ინფორმაცია:

პირველ სტრიქონში შემოდის ერთი ინტეჯერი n (1 ≤ n ≤ 2·105) - გადაცემების რაოდენობა.

ყოველ მომდევნო n სტრიქონში შემოდის ორი ინტეჯერი li და ri (0 ≤ li < ri ≤ 109) - დაწყების და დამთავრების დრო i-რი გადაცემისთვის.

გამოსატანი ინფორმაცია:

თუ პოლიკარპს შეუძლია, რომ უყუროს ყველა გადაცემას ორი ტელევიზორით, მაშინ უნდა დაბეჭდოთ YES, წინააღმდეგ შემთხვევაში კი უნდა დაბეჭდოთ NO.

მაგალითები:

input

3
1 2
2 3
4 5

output

YES

input

4
1 2
2 3
2 3
1 2

output

NO

Input

5

1 3

1 4

4 10

5 8

9 11

Output

YES

  1. თავდაპირევლად ჩართავს პირველ და მეორე გადაცემას. (1-2, 2-3) და შემდეგ რომელიმეს ჩაანაცვლებს 4-5 გადაცემით. (YES)

  2. თავდაპირველად აუცილებლად უნდა ჩართოს პირველი და მეოთხე გადაცემა. (1-2, 1-2), თუმცა ამ ორი გადაცემის ჩანაცვლებას ვეღარ ახერხებს, რადგან დარჩენილი გადაცემები ყველა 2ზე იწყება. (NO)

  3. თავდაპირველად ჩართავს პირველ და მეორე გადაცემას (1-3, 1-4). ამის შემდეგ პირველს ჩაანაცვლებს მესამეთი, ხოლო მეორეს მეოთხეთი და ახლა ჩართული ექნება (4-10, 5-8). ბოლოს კი რომელიმეს(არ აქვს მნიშვნელობა რომელს) ჩაანაცვლებს მეხუთეთი. (YES)


 

ინფორმაციის წაკითხვისას ყოველი გადაცემა შევინახოთ pair სტრუქტურის საშუალებით, სადაც წყვილის პირველი ელემენტი იქნება გადაცემის დაწყების დრო, ხოლო მეორე ელემენტი დამთავრების დრო. ყველა გადაცემა (ანუ ყველა წყვილების სტრუქტურა) კი ჩავყაროთ ვექტორში.

პოლიკარპმა გადაცემების ყურება უნდა დაიწყოს ისეთი გადაცემებით, რომელიც ყველაზე ადრე იწყება. წინააღმდეგ შემთხვევაში ასეთ გადაცემებს ის შემდგომში ვერანაირად ვერ უყურებს. ამიტომ ჩვენი ვექტორი დავასორტიროთ გადაცემების დაწყების დროის მიხედვით. თუ გვაქვს გადაცემების ასეთი სია:

2 4       დასორტირების შემდეგ  იქნება       1  2
3 2                                         2  3
2 3                                         2  4
1 2                                         3  2

 

დასორტირების შემდეგ ჩვენს ვექტორს უნდა გამოვყვეთ მარცხნიდან და ყოველ ჯერზე უნდა განვიხილოთ სამი გადაცემა (თუ გადაცემების რაოდენობა 3 ზე ნაკლებია ავტომატურად YES დაბრუნდება). ანუ თავდაპირველად განვიხილავთ ვექტორის 0 1 2 ინდექსებს, შემდეგ 1 2 3 ინდექსებს..... და ბოლოს განვიხილავთ n – 3 n – 2 n – 1 ინდექსებს.

თუ შესაძლებელია ისე, რომ ყოველ ჯერზე მარცხენა ორი გადაცემიდან ერთ-ერთის ჩანაცვლება მესამეთი მოხერხდეს, მაშინ პოლიკარპს შეუძლია ყველა გადაცემის ყურებაც. თუ ერთხელ მაინც ვერ მოხერხდება მესამე გადაცემით რომელიმეს ჩანაცვლება, მაშინ შეგვიძლია შევწყვიტოთ შემოწმება და დავაბრუნოთ უარყოფითი პასუხი.

ყოველი სამეულის განხილვისას, ჯერ შევადაროთ პირველი ორი ერთმანეთს დამთავრების დროის მიხედვით და რომელიც უფრო ადრე მთავრდება ის მოვაქციოთ სამეულში ყველაზე მარცხნივ. ამის შემდეგ სწორედ მარცხენა ელემენტი შევადაროთ მესამეს(რადგან ახალი გადაცემით ისეთი გადაცემა ჩავანაცვლოთ, რომელიც უფრო ადრე მთავრდება), თუ მესამეს დაწყების დრო მეტია ვიდრე პირველის დამთავრების, მაშინ წარმატებულად ჩანაცვლდება და უკვე ახალი სამეული განხილვას დავიწყებთ, წინააღმდეგ შემთხვევაში პასუხი უარყოფითია.

დავუშვათ ჩვენი დასორტირებული ვექტორი ასეთია:

1  4    თავდაპირველად განვიხილავთ სამეულს  1  4     შევადაროთ პირველი ორი დამთავრების დროის 
2  3                                                                                 2  3     მიხედვით,  რადგან მეორე უფრო ადრე მთავრდება,
4  5                                                                                 4  5     ვიდრე პირველი, მათ ადგილები უნდა გავუცვალოთ.
5  6


2  3    უკვე ადგილები რადგან გავუცვალეთ,         1  4    რადგან ამ სამეულში პირველი უფრო მალე 
1  4    პირველის დამთავრების დრო, მესამის        4  5    მთავრდება, ვიდრე მეორე, ადგილების გაცვლა 
4  5    დაწყებას უნდა შევადაროთ.  4 > 3,                5   6    საჭირო არ არის. პირდაპირ შეგვიძლია პირველის 
          ამიტომ წარმატებულად ჩანაცვლდება                    დამთავრების დრო, მესამის დაწყებას შევადაროთ. 
          და ახლა უკვე ასეთ სამეულს განვიხილავთ.          5 > 4, ანუ შეგვიძლია ჩავანაცვლოთ. რადგან ეს ბოლო
                                                                                                   სამეული იყო, პასუხი არის YES.