ფოტოგრაფია

დროის ლიმიტი: 1 წმ

მეხსიერების ლიმიტი: 64 მეგაბაიტი

შემავალი მონაცემები: stdin

გამომავალი მონაცემები: stdout

წყარო: USACO, 2012/13,OPEN, BRONZE


ბუბას უნდა, რომ გადაუღოს სურათი თავის N ცალ (2 <= N <= 1,000,000,000) სტუმარს, რომლებიც დგანან მწკრივში და გადანომრილი არიან 1..N. თითოეულ ფოტოზე შეიძლება ასახულ იქნეს მთლიანი მწკრივის რომელიღაც მონაკვეთი და ჯონს უნდა, რომ ნებისმიერი სტუმარი იყოს თუნდაც ერთ სურათში. სამწუხაროდ, სტუმრებს შორის არის K ცალი (1 <= K <= 1000) ერთმანეთისადმი მტრულად განწყობილი წყვილი, რომლებსაც არ უნდათ, რომ დაფიქსირდნენ ერთ ფოტოზე. ამ წყვილთა მოცემული განლაგებისათვის გამოთვალეთ გადასაღებ ფოტოთა მინიმალური რაოდენობა.

შეტანის ფორმატი:

* სტრიქონი 1: ჰარით გამოყოფილი ორი მთელი რიცხვი N და K.

* სტრიქონები 2..K+1: სტრიქონი i+1 შეიცავს ორ მთელ რიცხვს, A_i და B_i, რაც გვიჩვენებს, რომ A_i და B_i ნომერი ძროხები მტრულად არიან ერთმანეთისადმი განწყობილი და ერთ სურათში არ უნდა გამოჩნდნენ.

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

* სტრიქონი 1: ერთი მთელი რიცხვი - გადასაღებ ფოტოთა მინიმალური რაოდენობა.




მაგალითები

შესატანი მონაცემები
7 3 1 3 2 4 5 6 დაკოპირება
გამოსატანი მონაცემები
3 დაკოპირება

შენიშვნა

გამოტანის განმარტება: ბუბა გადაიღებს 3 ფოტოს: - ერთში იქნებიან სტუმრები 1 დან 2-მდე. - მეორეში იქნებიან სტუმრები 3 დან 5-მდე. - მესამეში იქნებიან სტუმრები 6-დან 7-მდე.