مارک و خواهرش می‌خواهند برخی مکان‌های دیدنی در زیباشهر را بازدید کنند. برای برنامه‌ریزی گردششان، آن‌ها یک نقشه خریدند که هم مکان‌های دیدنی اصلی شهر را نشان می‌دهد (به همراه موقعیت جغرافیایی آن‌ها) و هم خیابان‌هایی که به آن مکان‌هایی دیدنی میرسند. خیابان‌ها یا مخصوص پیاده‌روی هستند یا دوچرخه‌سواری. از ‌آن‌جایی که مارک عاضق دوچرخه‌سواری است، او تصمیم گرفته که با یک دوچرخه از شهر دیدن کند. از طرف دیگر، خواهرش که از دوچرخه‌سواری بی‌زار است تصمیم گرفته که پیاده‌روی کند. آن‌ها با هم توافق کرده‌اند که گشت و گذارشان را از ایستگاه مرکزی قطار شروع کنند و در ایستگاه غربی قطار به پایان برسانند که هر دو از مکان‌های دیدنی هستند و در نقشه وجود دارند. از آن‌جایی که مکان‌های دیدنی بسیار زیبا هستند، آن‌ها تصمیم گرفتند که حداقل یک شب را در هر یک از مکان‌های دیدنی در مسیرشان بگذرانند (لزوما همه آن‌ها در شهر نیستند). خوشبختانه رفتن از یک مکان دیدنی به دیگری طی چند ساعت در یک روز با دوچرخه یا پیاده امکان‌پذیر است. از آن‌جایی که چادر زدن در خیابان‌ها ممنوع است، آن‌ها تصمیم گرفتند که در نزدیکی مکان دیدنی که هر شب از آن بازدید می‌کنند چادر بزنند و هر شب پیش از خواب با یکدیگر صحبت کنند. برای برقراری چنین تماس‌هایی آن‌ها تصمیم گرفتند که یک جفت رادیو دوطرفه بخرند که برای تماس‌های رادیویی به کار می‌رود. از آن‌جایی که هر رادیوی دوطرفه‌ای بازه‌ی پوشش رادیویی محدود دارد و قیمت آن بستگی به بازه‌ی پوشش رادیویی آن دارد، ‌آن‌ها می‌خواهند مسیرهایی بیابند (مسیر با دوچرخه و مسیر پیاده) که بازه‌ی پوشش رادیویی کمینه شود. از آن‌جایی که محاسبه این مقدار با دست ساده نیست، آن‌ها سوالشان را به مسابقه‌ی برنامه‌نویسی ACM در تهران فرستادند تا جواب خود را به صورت بهینه بیابند.

ورودی شامل چندین مورد آزمون است. هر مورد آزمون یک گراف است که نقشه را مدلسازی می‌کند: رئوس و یال‌ها به ترتیب نمایش دهنده‌ی مکان‌های دیدنی و خیابان‌ها هستند. خط اول هر مورد آزمون شامل دو عدد صحیح نامنفی $n$ و $m$ می‌باشد که $n \leq 50$ تعداد رئوس و $m$ تعداد یال‌هاست. در هر یک از $n$ خط بعدی، خط $i$ام شامل $x$ و $y$ مختصات راس با شناسه‌ی ‌$i$ هستند. سپس ورودی با $m$ خط ادامه می‌یابد که توصیف کننده‌ی یال‌ها هستند. هر خط شامل دو شناسه راس است (که یال را تعریف می‌کنند) و یک نویسه‌ی «W» یا «B». «W» به معنی آن است که یال، یک خیابان مخصوص پیاده‌روی است و «B» یعنی یال، یک خیابان مخصوص دوچرخه‌سواری است. دقت کنید که بین دو مکان دیدنی ممکن است هم خیابان پیاده‌روی باشد و هم خیابان دوچرخه‌سواری. در نهایت در آخرین خط، به ترتیب شناسه‌ی ایستگاه‌های مرکزی و غربی داده شده‌اند. می‌توانید فرض کنید که مسیرهای پیاده روی و دوچرخه‌سواری بین ایستگاه‌های مرکزی و غربی وجود دارد و همه ‌اعداد، صحیح و نامنفی کمتر از $10^4$ هستند. ورودی با «0 0» خاتمه می‌یابد.

به ازای هر مورد آزمون شما باید در یک خط مربع کمینه‌ی بازه‌ی پوشش رادیویی را چاپ کنید.

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

• سوال قبل