====== لحیم‌کاری ======


یک مدار چاپی با $n$ نقطه روی آن داده شده است. این نقاط روی یک خط مستقیم هستند و مختصات نقطه‌ی $i$ برابر $(i,0)$ است $(1\leq i \leq n)$. $m$ زوج  از این نقاط را می‌خواهیم دو به دو به هم لحیم کنیم. مسیر لحیم‌کاری بین دو نقطه‌ی $i$ و $j$ به صورت شکل زیر نشان داده شده است.
{{ :سوالات_المپیاد:دوره‌ی_انتخاب_تیم:دوره‌ی_۳:لحیم.png |}}

این مسیر را به سه‌تایی مرتب $(i,j,h)$ نشان می‌دهیم که $h$ ارتفاع این مسیر نامیده می‌شود و عددی صحیح است. (توجه نمایید که $h$ ممکن است صفر، مثبت و یا منفی باشد.) هدف این مسئله این است که این نقاط را طوری به هم لحیم کنیم که مسیرهای لحیم‌کاری یک‌دیگر را قطع نکنند.

برنامه‌ای بنویسید که با دریافت $n$ و $m$ زوج نقطه،

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



===== ورودي =====

در سطر اول فایل ورودی این برنامه، به ترتیب مقادیر $n$ و $m$ و در $m$ سطر بعدی، در هر سطر دو عدد قرار دارد که نشان‌دهنده‌ی یکی از زوج نقاطی هستند که قرار است به هم لحیم شوند. فرض کنید که که $m\leq 100$ و هیچ دوتایی از زوج نقاط، ابتدا و انتهای مشترکی ندارند.


===== خروجي =====

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

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

<WRAP :en>
^  ورودي نمونه  ^  خروجي نمونه  ^
|12 5 \\ 1 10 \\ 2 9 \\ 3 7 \\ 4 6 \\ 8 12 | ‎1 10 2 \\ 2 9 1 \\ 3 7 -1 \\ 4 6 0 \\ 8 12 -1 \\ Maximum absolute value of heights = 2 |

</WRAP>

  * [[سوال ۳|سوال بعد]]
  * [[سوال ۱|سوال قبل]]