====== راه فرار مستقیم ======


یک توری $N\times N$ $(N\leq 100)$ داده شده است. نقاط این توری با مختصات $(i,j)$ مشخص می‌شوند. مختصات نقطه‌ی واقع در گوشه‌ی سمت چپ و پایین توری $(0,0)$ و مختصات نقطه‌ی واقع در گوشه‌ی بالا و سمت راست $(N-1,N-1)$ است. هر نقطه مانند $(i,j)$ از این توری به چهار نقطه‌ی $(i,j \pm 1)$ و $(i\pm 1 , j)$ در صورت وجود وصل است.

$M$ نقطه در این توری داده شده‌اند. می‌خواهیم هر یک ا ز این نقطه‌ها را با مسیری مستقیم به عنوان راه فرار به یکی از نقاط مرزی توری وصل کنیم، به طوری که این مسیرها یک‌دیگر را قطع نکنند $(M\leq 100)$.

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


===== ورودي =====
در فایل ورودی چند مجموعه داده که با یک سطر فاصله‌ی خالی از هم جدا شده‌اند قرار دارد. در سطر اول هر مجموعه داده‌ی ورودی به ترتیب اعداد $N$ و $M$ و در $M$ سطر بعد، مختصات $M$ نقطه از توری قرار دارند.


===== خروجي =====
در فایل خروجی که در آن خروجی مربوط به هر مجموعه داده با یک سطر خالی از هم جدا می‌شوند. شکل خروجی مربوط به هر مجموعه داده به این صورت است: در صورتی که قسمت (۱) جواب داشته باشد، در $M$ سطر، در هر سطر مختصات یک نقطه‌ی ورودی و جهت راه فرار آن را بنویسید. جهت‌های راست، چپ و پایین را به ترتیب با نویسه‌های $R$، $L$ و $D$ مشخص کنید. در صورتی که قسمت (۱) جواب نداشته باشد، ابتدا پیغام زیر را بنویسید:

$$Part \quad 1 \quad has \quad no \quad solution.$$

و در سطر‌های بعد، در صورتی که قسمت (۲) جواب داشت، جواب آن را به همین صورت و در غیر این صورت پیغام زیر را بنویسید.

$$Part \quad 2 \quad has \quad no \quad solution.$$


به مثال زیر توجه کنید. مجموعه داده‌های اول و دوم این مثال در شکل زیر نشان داده شده است. همان‌طور که در مثال مشاهده می‌کنید در مورد مجموعه داده‌ی سوم هیچ یک از دو قسمت مسئله جواب ندارد.


{{ :سوالات_المپیاد:دوره‌ی_انتخاب_تیم:دوره‌ی_۳:فرار.png |}}

===== ورودي و خروجي نمونه =====

<WRAP :en>
^  ورودي نمونه  ^  خروجي نمونه  ^
|12 7 \\ 5 1 \\ 2 6 \\ 5 5 \\ 7 4 \\ 9 2 \\ 8 6 \\ 8 9 \\ \\ 12 11 \\ 3 1 \\ 5 2 \\ 10 1 \\ 3 4 \\ 6 4 \\ 11 4 \\ 4 6 \\ 6 7 \\ 3 10 \\ 9 10 \\ 10 10 \\  \\ 8 7 \\ 1 3 \\ 3 3 \\ 5 3 \\ 3 5 \\ 6 5 \\ 4 7 \\ 7 5 | ‎5 1 D \\ 2 6 D \\ 5 5 R \\ 7 4 D \\ 9 2 R \\ 8 6 R \\ 8 9 R \\ Part 1 has no solution. \\ 3 1 D \\ 5 2 D \\ 10 1 R \\ 3 4 L \\ 6 4 D \\ 11 4 R \\ 4 6 D \\ 6 7 L \\ 3 10 L \\ 9 10 D \\ 10 10 R \\  \\ Part 1 has no solution. \\ Part 2 has no solution. ‎|

</WRAP>



  * [[سوال ۶|سوال بعد]]
  * [[سوال ۴|سوال قبل]]