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

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

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

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

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

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

• سوال بعد
• سوال قبل