پاسخ - SGU 213
متن اصلی سوال : http://acm.sgu.ru/problem.php?contest=0&problem=213
ترجمه : شما در یک کهکشان زندگی می کنید که در آن N ستاره وجود دارد و شما اهل ستاره‌ی شماره S هستید. در این کهکشان می توان مستقیما از ستاره‌ای به ستاره‌ای دیگر رفت اگر و تنها اگر بین آنها خط هوایی فضایی باشد. به تازگی حکومت ستاره‌ی شماره T با حکومت ستاره‌ی شماره S وارد جنگ شده، شما به عنوان فرمانده وظیفه دارید برای همایت از مهین خود راه رسیدن به سیاره‌ی خود را بر حکومت ستاره‌ی شمارهی T ببنید. هر خط هوایی فضایی بین دو ستاره بسته می‌شود اگر شما یک کشتی فضایی در آن مستقر کنید. به دلیل زیاد بودن منابع شما هیچ محدودیتی در تعداد کشتی‌ها ندارد ولی تنها مشکلی که شما دارید این است که هر کشتی یه قطعه‌ی کنترل کننده‌ی سری به نام کریستال دارد. ما می‌دانیم دشمن به اطلاعات همه‌ی کریستال‌هایی که ما استفاده خواهیم کرد به جز یکی دسترسی خواهد داشت. حالا باید کشتی ها را به گونه‌ای مستقر کنیم که اگر همه‌ی کریستال‌ها به جز یکی هم لو رفت مسیری از ستاره T به ستاره ما وجود نداشته باشد. در ضمن برای امنیت بیشتر باید تا انجایی که می توانیم از کریستال‌های مختلف استفاده کنیم (در تعداد و انواع کربستال ها محدودیت نداریم)
به شما عدد N و اطلاعات خطوط هوایی فضایی بین ستاره‌ها داده می شود. شما باید تعداد حداکثر کریستال‌ها و محل قرار گیری کریستال‌های هر نوع را مشخص کنید به گونه‌ای که به ازای هر نوع کریستال، اگر بقیه کریستال‌ها لو بروند، کشتی‌هایی که این کریستال را دارند امنیت را برای ستاره‌ی ما حفظ کنند. توجه داشته باشید در هر خط هوایی فضایی بین ستاره ای می‌توان حداکثر یک کشتی فضایی قرار داد.
در کهکشان ما هیچ خط هوایی فضایی یک ستاره را به خودش وصل نمی‌کند.
ورودی :
در خط اول ورودی به اعداد N و M و S و T که به ترتیب نشان دهنده‌ی تعداد ستاره‌ها، تعداد خطوط هوایی فضایی، شماره ستاره‌ی شما و شمارهی ستاره دشمن می آید.
در M خط بعدی اطاعات خطوط هوایی فضایی می‌آید. در خط i+1 ام دو عدد نشان دهنده‌ی دو سر خط هوایی فضایی i ام می‌آید.
خروجی :
در خط اول خروجی L، یعنی حداکثر تعداد کریستال های قابل استفاده را چاپ کنید. در L خط بعدی در خط i+1 ام خروجی، شماره خطوط هوایی فضایی که یک کشتی با کریستال از نوع i در آن قرار داده‌اید را چاپ کنید.
راهنمایی :
1 . کوتاه ترین مسیر از ستاره S به ستاره T را پیدا کنید.
2 . در هر مسیر که بین این دو ستاره وجود دارند باید از همه‌ی انواع کریستال ها استفاده شده باشد.
