یک روز به شنگول و منگول، گراف جهتدار نیمهزیبای G را دادند و بهشان گفتند که در این گراف، اندازه بزرگترین «مجموعهی نامهربان» را پیدا کنید. اگر نمیدانید «گراف جهتدارِ نیمهزیبا« یا «مجموعهی نامهربان« چیست (بالطّبع نمیدونین!) ، متن زیر را بخوانید.
به یک گراف جهتدار G نیمهزیبا گویند، اگر که زیر مجموعهای دلخواه از راسهایش انتخاب شده باشند. این زیر مجموعه را «مجموعه راسهای زیبا« مینامیم!
به مجموعهی S از راسها در گراف جهتدار G «نامهربان» گویند اگر S زیر مجموعهی «مجوعه راسهای زیبا« بوده و هر راس دلخواه v از آن، سه خاصیت زیر را داشته باشد :
حالا به شنگول و منگول کمک کنید تا «اندازه» بزرگترین مجموعهی نامهربان در گراف G را پیدا کنند.
در خروجی تنها یک عدد چاپ کنید که نشان دهنده اندازهی بزرگترین زیر مجموعهی نامهربان باشد.