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

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

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