====== مجموعه‌ی نامهربان ====== یک روز به شنگول و منگول، گراف جهت‌دار نیمه‌زیبای ‎$G$‎ را دادند و بهشان گفتند که در این گراف، اندازه بزرگ‌ترین «مجموعه‌ی ‎نامهربان»‎ را پیدا کنید. اگر نمی‌دانید «‎گراف جهت‌دارِ نیمه‌زیبا‎«‎ یا «‎مجموعه‌ی نامهربان‎«‎ چیست (بالطّبع نمی‌دونین‎!) ، متن زیر را بخوانید. به یک گراف جهت‌دار ‎$G$‎ نیمه‌زیبا گویند، اگر که زیر مجموعه‌ای دلخواه از راس‌هایش انتخاب شده باشند. این زیر مجموعه را «‎مجموعه راس‌های زیبا‎«‎ می‌نامیم‎!‎ به مجموعه‌ی ‎$S$‎ از راس‌ها در گراف جهت‌دار ‎$G$ «نامهربان»‎ گویند اگر ‎$S$‎ زیر مجموعه‌ی «‎مجوعه راس‌های زیبا‎«‎ بوده و هر راس دلخواه ‎$v$‎ از آن، سه خاصیت زیر را داشته باشد : * $v$‎ به حداقل یک راس از ‎$S$‎ یال داشته باشد. * حداقل یک راس از ‎$S$‎ به ‎$v$‎ یال داشته باشد. * $v$‎ به راس‌هایی که عضو ‎$S$‎ نیستند، یال نداشته باشد. حالا به شنگول و منگول کمک کنید تا ‎«اندازه»‎ بزرگ‌ترین مجموعه‌ی نامهربان در گراف ‎$G$‎ را پیدا کنند. ===== ورودی ===== * در سطر اول ورودی، به ترتیب دو عدد ‎$n$‎ و ‎$m$‎ داده‌ شده است که ‎$n$‎ برابر تعداد راس‌های گراف و $m$‎ برابر تعداد یال‌های گراف می‌باشد. * در هر سطر از ‎$m$‎ سطر بعدی، به ترتیب دو عدد متفاوت $v_i$‎ و ‎$v_j$‎ آمده، به این معنا که راس ‎$v_i$‎ به راس ‎$v_j$‎ یال دارد. * در سطر آخر ورودی، ‎$n$‎ عدد آمده است، عدد ‎$i$‎ام این دنباله برابر ‎$1$‎ است اگر که راس ‎$i$‎ام،رعضو مجموعه راس‌های زیبا باشد و برابر ‎$0$‎ است اگر که راس ‎$i$‎ام، عضو مجموعه راس‌های زیبا نباشد. * $0 \leq n \leq 100000$‎ * $0 \leq m \leq 1000000$‎ ===== خروجی ===== در خروجی تنها یک عدد چاپ کنید که نشان دهنده اندازه‌ی بزرگ‌ترین زیر مجموعه‌ی نامهربان باشد. ===== محدودیت‌ها ===== * محدودیت زمان: ۱ ثانیه * محدودیت حافظه: ۲۵۶ مگابایت ===== ورودی و خروجی نمونه ===== ^ ورودی نمونه ^ خروجی نمونه ^ |3 4 \\ 1 2 \\ 1 3 \\ 2 3 \\ 3 2 \\ 1 1 1 | 2 | * [[سوال ۵|سوال بعد]] * [[سوال ۳|سوال قبل]]