ოფისების განაწილება

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

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

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

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

წყარო: პოლონეთი, ოლიმპიადა 14, ეტაპი 1


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

 შემომავალი მონაცემები:  პირველი ხაზი შეიცავს ორ რიცხვს n და m-ს (2 <= n <= 100 000, 1 <= m <= 2 000 000), რომლებიც არიან ერთი დაშორებით გამოყოფილები და აღნიშნავენ(მიმდვერობის შესაბამისად): ბაიტელის თანამშრომელთა რაოდენობას და ისეთი წყვილების რაოდენობას, რომელთაც ერთმანეთის ნომერი ტელეფონში უწერიათ. კომპანიის თანამშრომლები არიან გადანომრილი 1-დან n-ის ჩათვლით.   მომდევნო m ცალი ხაზი შეიცავს ერთი დაშორებით გამოყოფილ რიცხვთა წყვილს ai და bi (1 <= ai <= bi <= n, 1 <= i <= m -სთვის). ეს ნიშნავს, რომ ai თანამშრომელს და bi  თანამშრომელს აქვთ ერთმანეთის ნომრები ჩაწერილი თავიანთ მიღებულ ტელეფონებში. თითოეული თანამშრომელთა წყვილი შემოვა მაქსიმუმ ერთხელ შემომავალ მონაცემებში. 

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




მაგალითები

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

შენიშვნა

თანამშრომლების კარგი განაწილების მაგალითი მდგომარეობს შემდეგში: თანამშრომელი N4 პირველ ოფისში, თანამშრომლები N5  და N7 მეორე ოფისში და თანამშრომლები N1, N2, N3  და N6 მესამე ოფისში.