$G$ یک گراف ساده با $N$ راس $(N\leq 100)$ است. در یک لحظه، یک پلیس و یک تبهکار روی دو راس مختلف از این گراف قرار گرفته‌اند. در همین لحظه، فرد تبهکار شروع به حرکت کرده، یک مسیر مشخص را (که می‌تواند شامل راس تکراری باشد، ولی تعداد رئوس آن مجموعا از ۱۰۰ بیش‌تر نیست) می‌پیماید. پلیس مسیر حرکت تبهکار را از قبل می‌داند و می‌خواهد مسیر حرکتش را طوری تعیین کند که هر چه زودتر بتواند او را دستگیر کند. برای این منظور، کافی است مسیری به یکی از راس‌های مسیری که تبهکار می‌پیماید پیدا کند که با طی آن مسیر بتواند زودتر از تبهکار و یا حداقل هم‌زمان با او به آن برسد. پلیس را در انجام این کار یاری دهید!

به هر یک از یال‌های گراف یک عدد صحیح و مثبت کم‌تر از ۳۰۰۰۰ به عنوان وزن، نسبت داده شده است. عبور از هر یال، چه برای تبهکار و چه برای پلیس به اندازه‌ی وزن آن یال زمان می‌برد. فرض کنید مجموع وزن یال‌های مسیری که تبهکار قرار است بپیماید، در یک متغیر ( Lognit و نه یک متغیر Integer) جا می‌گیرد.

در سطر اول فایل ورودی عدد $N$ و شماره‌ی راسی که پلیس در ابتدا در آن قارا گرفته نوشته شده است. (راس‌ها شماره‌های ۱ تا $N$ دارند.) پس از این در $N-1$ سطر بعد، نیمه‌ی پایین ماتریس وزن‌های گراف $G$‌آ«ده است. اگر یال ی بین راس $i$ و راس $j$ وجود داشته باشد، درایه‌ی $(i,j)$ این ماتریس برابر با وزن این یال و در غیر این صورت صفر است. در نهایت در سطر آخر فایل ورودی، یک دنباله از شماره‌ی راس‌های $G$، که مسیر تبهکار را مشخص می‌کند، نوشته شده است. انتهای این دنباله با یک عدد 0 مشخص می‌شود.

در سطر اول فایل خروجی زمانی که از شروع حرکت طول می‌کشد تا تبهکار دستگیر شود و در سطر دوم مسیر را که پلیس باید بپیماید تا بتواند تبهکار را در این زمان دستگیر کند بنویسید. در صورتی که امکان ندارد پلیس بتواند تبهکار را تا قبل از پایان پیمودن مسیرش دستگیر کند، پیغام NO SOLUTION را در این فایل بنویسید.

• سوال بعد
• سوال قبل