المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی انتخاب تیم:دوره ی ۱۵:سوال ۵

Circle

کوشا تعدادی دایره بر روی صفحه نقاشی کرده و بعضی از آن‌ها را با خط به یک‌دیگر متصل ساخته است. سپس هر دایره را به یکی از رنگ‌های قرمز، سبز یا آبی( که ترتیب با حروف $G،R$ و $B$ نمایش داده می‌شوند) درآورده است. کوشا نقاشی‌اش را به پدربزرگ نشان می‌دهد. پدربزرگ برای این‌که قدرت حل مسئله‌ي کوشا را بسنجد، به وی می‌گوید که دایره‌هایی که به یک‌دیگر اتصال دارند، نباید هم‌رنگ باشند؛ کوشا متوجه هدف پدربزرگ می‌شود و برای این که توانایی ذهنی خود را بیش‌تر به پدربزرگ ثابت کند، تصمیم می‌گیرد که طوری دایره‌ها را دوباره رنگ‌آمیزی کند، که علاوه بر برقرار کردن شرط پدربزرگ، رنگ هر دایره‌ای تغییر کرده باشد!

شما باید تعیین کنید که آیا کوشا می‌تواند به این مهم دست یابد یا خیر.

برنامه‌ای بنویسید که:

  • تعداد و رنگ دایره‌ها و نیز توصیف خطوط بین آن‌ها را از ورودی بخواند.
  • پاسخی برای خوسته‌ی پدربزرگ و کوشا بیابد.
  • پاسخ را در خروجی بنویسد.

ورودی

سطر نخست ورودی شامل دو عدد صحیح است: $n$ و $m$ که به ترتیب تعداد دایره‌ها و خطوط رسم شده بین آن‌هاست( $1 \leq n \leq 1000$ و $1 \leq m \leq 20000$). سطر بعدی محتوی $n$ حرف از مجموعه‌ی $\{R,G,B \}$ می‌باشد؛ حرف $i$ام نشانگر رنگ اولیه‌ی دایره‌ی $i$ام است. هر یک از $m$ سطر دارای دو عدد صحیح است که دو دایره‌ی به هم متصل را معرفی می‌نماید؛ دایره‌ها با شماره‌های ۱ تا $n$ نشان داده می‌شوند.

خروجی

در تنها سطر خروجی یک رشته‌ی $n$ حرفی از مجموعه‌ی $\{R,G,B \}$ برای رنگ‌آمیزی مجدد دایره‌ها بنویسید. اگر چند راه‌حل وجود دارد، فرقی نمی‌کند کدام یک را بنویسید؛ اگر هیچ راه‌حلی وجود ندارد، رشته‌ی $Impossible$ را به عنوان خروجی تولید کنید.

محدودیت‌ها

  • محدودیت زمان: ۵ ثانیه
  • محدودیت حافظه: ۶۴ مگابایت

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

ورودی نمونه خروجی نمونه
4 5
RRRG
1 3
1 4
3 4
2 4
2 3
BBGR
4 5
RGRR
1 3
1 4
3 4
2 4
2 3
Impossible

ابزار صفحه