المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره‌ی تابستان:دوره‌ی ۱۴:عملی:سوال ۱۶

کشور دوم

در کشور المپیادی‌ها تعدادی شهر وجود دارد. بین برخی از شهرهای این کشور جاده وجود دارد. از آن‌جا که المپیادی‌ها آدم‌های باهوشی هستند، در ساختن کشور از کم‌ترین تعداد جاده استفاده کرده‌اند. بالطبع آن‌ها از قوانین ساخت کشور پیروی کرده‌اند، در هر کشوری می‌توان از هر شهری به هر شهر دیگر رفت. منظور از فاصله‌ی دو شهر طول کوتاه‌ترین مسیری است که این دو شهر را به هم وصل می‌کند. به یک شهر منطقه‌ی محروم می‌گوییم اگر و فقط اگر به آن شهر حداکثر یک جاده متصل باشد. رئیس‌جمهور دستور داده است که دورترین منطقه‌ی محروم از شهر خود را بیابند. از آن‌جایی که فرمانداران کلیه‌ی شهرها از اعضای کمیته‌ی کامپیوتر هستند، با توجه به برگزاری دوره‌ی تابستان از موقعیت استفاده کرده از شما درخواست می‌کنند که این کار را برای آن‌ها انجام دهید.

ورودی

در سطر اول ورودی به ترتیب $e$ و $n$ تعداد شهرها و تعداد جاده‌های کشور به شما داده شده است. سپس در $e$ سطر در هر کدام دو سر یکی از جاده‌ها داده شده است. ($n\leq 10^6$ و $e\leq 10^8$)

خروجی

شما می‌بایستی در سطر $i$ ام از فایل خروجی، ابتدا شماره‌ی دورترین منطقه‌ی محروم از شهر $i$ ام سپس طول کوتاه‌ترین مسیر از شهر $i$ به آن شهر را بنویسید. (در صورت وجود چند شهر با بیش‌ترین فاصله شما می‌توانید هر کدام از آن‌ها را به دلخواه خود در خروجی بنویسید.)

ورودي و خروجي نمونه

ورودي نمونه خروجي نمونه
3 2
1 2
3 2
3 2
3 1
1 2

ابزار صفحه