اطلاعات فردی

عدد چاپ‌کن

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- زمان گذشته‌است و لیته و فیته به خوبی و خوشی به زندگی ادامه می‌دهند، اما زندگی همیشه با چالش همراه بوده‌است. چند‌روزی است که دوستان قدیمی لیته مثل مهرسا، مهسا، السا، درسا، پریسا، آیسا، و ... به سراغ او آمده‌اند و بعضی اوقات با او چت می‌کنند. لیته که در این موارد آدم بسیار زبده‌ای است، به خوبی می‌تواند با استفاده از پیام‌های روز قبل آن‌ها، پیش‌بینی کند که در روز بعد در چه زمان‌هایی به او پیام می‌دهند و تا چه زمانی می‌توانند منتظر جواب بمانند. هم‌چنین با توجه به برنامه‌ریزی دقیقی که همیشه دارد، می‌تواند این را نیز بگوید که در روز آتی توانایی چت‌کردنش چه‌قدر زیاد خواهد بود، یعنی در یک دقیقه حداکثر با ‌چند نفر می‌تواند چت کند. چالشی که وجود دارد این است که آیا او می‌تواند در زمان‌هایی که دوستانش انتظار دارند به آن‌ها جواب بدهد یا خیر. **توجه** کنید که جواب دادن به هر نفر **دقیقا یک دقیقه** طول می‌کشد، چه با کس دیگری همزمان باشد، چه تنها نفری باشد که لیته در‌ حال جواب دادن به اوست. # ورودی سطر اول ورودی شامل دو عدد طبیعی $n$ و $k$ است که با فاصله از هم آمده‌اند. عدد $n$ نشاندهنده تعداد افرادی است که به لیته پیام خواهند داد. عدد $k$ نشاندهنده توانایی چت کردن لیته است، یعنی او ‌می‌تواند همزمان با $k$ نفر چت کند. در هر کدام از $n$ سطر بعد اطلاعات نفر $i$-اُم که به لیته پیام می‌دهد، آمده‌است. این سطر شامل دو عدد صحیح $l$ و $r$ است و یعنی نفر $i$-اُم در دقیقه $l$ به لیته پیام‌ می‌دهد و حداکثر تا دقیقه $r$ منتظر جواب لیته می‌ماند. * به ازای نفر $i$-اُم لیته می‌تواند از دقیقه $l$ تا دقیقه $r$ (شامل هر دو) به او جواب بدهد. $$1 \le k \le n \le 100\ 000$$ $$1 \le l \le r \le 100\ 000$$ # خروجی در تنها خط خروجی اگر لیته می‌تواند در زمان انتظار هرکس به او جواب بدهد، `YES` چاپ کنید و در غیر این‌صورت `NO` چاپ کنید. ## ورودی نمونه ۱ ``` 3 2 1 2 1 100 1 1 ``` ## خروجی نمونه ۱ ``` YES ``` توضیحات: لیته در زمان ۱ مجبور است جواب نفر سوم را بدهد. در همان زمان(زمان ۱) جواب نفر دوم را هم می‌دهد. سپس در زمان ۲، جواب نفر اوّل را هم می‌دهد. ## ورودی نمونه ۲ ``` 3 2 3 3 3 3 3 3 ``` ## خروجی نمونه ۲ ``` NO ``` توضیحات: لیته مجبور است در زمان ۳ جواب هر ۳ نفر را بدهد. ولی ظرفیت لیته ۲ نفر است. پس جواب این تست `NO` خواهد بود.

نمک زندگی

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- آی مجری که به فکر بچه‌ها است، می‌خواهد آن‌ها را به یک اردوی علمی ببرد. در این اردو او آن‌ها را به خارج از شهر (در یک بیابان) برده و در آنجا یک مسابقه‌ی آموزشی برگزار می‌کند. آی مجری $n$ نقطه را در بیابان مشخص کرده و بین یکسری از نقاط خط کشیده به طوری که از هر نقطه به هر نقطه‌ی دیگری دقیقا یک مسیر از روی خطوط وجود دارد. حال آی مجری روی هر خط و در طول مسیر بین دو نقطه مسائلی قرار می‌دهد که اگر کسی از روی آن‌ها عبور کند به اندازه‌ی سختی مسئله به علمش اضافه می‌شود. دقت کنید که سختی هر مسئله عددی **طبیعی** می‌باشد. آی مجری در اول کار به هرکس دو نقطه متفاوت را می‌دهد و می‌گوید باید از نقطه‌ی اول به نقطه‌ی دوم برود. علمی که به یک نفر اضافه می‌شود برابر است با مجموع علمی که در مسیر به دست می‌آورد. بچه‌ها اصلا دوست ندارند به اندازه‌ی هم به علمشان اضافه شود(مثلا اگر فامیل و جیگر به اندازه‌ی هم علم کسب کنند، فامیل بسیار ناراحت می‌شود). برای همین آی مجری می‌خواهد ببیند با تغییر مسائل حداقل و حداکثر چند نفر را می‌تواند با خود ببرد تا همه علم متفاوتی کسب کنند. # ورودی در سطر اول ورودی، عدد $n$ آمده‌است که نمایانگر تعداد نقاط است. $$1 \le n \le 100\ 000$$ سپس در $n - 1$ سطر بعدی در هر سطر دو عدد $x$ و $y$ می‌آید که یعنی نقطه‌ی $x$ به نقطه‌ی $y$ وصل است. تضمین می‌شود که ورودی شروط ذکر شده در صورت سوال را دارد. $$1 \le x, y \le n$$ # خروجی خروجی شامل دو عدد است که به ترتیب نشان‌دهنده‌ی حداقل و حداکثر تعداد بچه‌هاییست که آی مجری می‌تواند با خود ببرد و علمی که هرکدام کسب می‌کنند متفاوت باشد. # مثال ## ورودی نمونه ۱ ``` 2 1 2 ``` ## خروجی نمونه ۱ ``` 1 1 ``` ## ورودی نمونه ۲ ``` 4 1 2 2 3 3 4 ``` ## خروجی نمونه ۲ ``` 3 6 ```