ბილიკების გაყვანა

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

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

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

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

წყარო: USACO, 2002/03, FALL, ORANGE


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

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

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

* სტრიქონები 2..P+1: თითოეული სტრიქონი შეიცავს ჰარით გამოყოფილ ორ მთელ რიცხვს, რომლებიც აღწერენ ბილიკს. მთელი რიცხვები არიან ბილიკით შეერთებული მინდვრების ნომრები. ბილიკზე შეიძლება სიარული ორივე მიმართულებით. მინდვრები გადანომრილია 1-დან N-მდე.

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

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

 

 

 




მაგალითები

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