گراف ساده و بدون جهت G و همچنین زیردرخت فراگیر T از آن داده شده است. میخواهیم تمام رئوسی مثل v را بیابیم که دارای این خاصیت باشند: بتوان از راس v، DFS ای زد که درخت DFS حاصل از آن برابر T شود. توجه کنید که در DFS میتوانیم رئوس مجاور هر راس را به هر ترتیب دلخواهی پیمایش کنیم.
در فایل ورودی ابتدا n، تعداد رئوس گراف و m، تعداد یالهای آن آمده است. سپس در n−1 سطر بعد در هر سطر دو عدد به نشانه دو انتهای یک یال از T آمده است. بقیه یالهای گراف که در T نیامدهاند در m−n+1 سطر بعد به همین صورت میآیند.
در سطر اول فایل خروجی، k، تعداد رئوس دارای خاصیت فوق را بنویسید. سپس در k سطر بعد، شمارهی این رئوس را به ترتیب صعودی بنویسید. فرض کنید که n≤30000 و m−n≤100.
ورودي نمونه | خروجي نمونه |
---|---|
4 4 1 2 2 3 2 4 3 4 | 2 3 4 |