გრაფის ბმულობა

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

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

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

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

წყარო: USACO, 2015/16, OPEN, GOLD


მოცემულია N წვეროსა და M წიბოსაგან (1≤N,M≤200000) შედგენილი არაორიენტირებული გრაფი. ყოველ ბიჯზე გრაფიდან შლიან ერთ წვეროს. დაწერეთ პროგრამა, რომელიც დაადგენს, წარმოადგენენ თუ არა გრაფის წაუშლელი წვეროები ერთ ბმულ კომპონენტს. თავდაპირველი გრაფი შესაძლოა ბმული არ იყოს.

შესატანი მონაცემები: პირველ სტრიქონში ორი მთელი რიცხვი N და M. მომდევნო M სტრიქონიდან თითოეულში ორ-ორი რიცხვი - წიბოთა ჩამონათვალი. მომდევნო N სტრიქონიდან თითოეულში იმ წვეროების თანმიმდევრული ჩამონათვალი, რომელიც გრაფიდან წაშალეს.

გამოსატანი მონაცემები: პირველ სტრიქონში გრაფის თავდაპირველი მდგომარეობა, მომდევნო N-1 სტრიქონიდან თითოეულში კი გრაფის მდგომარეობა მორიგი წვეროს წაშლის შემდეგ. გრაფის მდგომარეობის აღსანიშნავად გამოიტანეთ სიტყვა "YES", თუ გრაფის წაუშლელი წვეროები ერთ ბმულ კომპონენტს წარმოადგენენ, წინააღმდეგ შემთხვევაში გამოიტანეთ სიტყვა "NO".

 



მაგალითები

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