المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۱۹:عملی:سوال ۹

Lost

پس از کشته شدن جان لاک و فقدان اعتماد افراد در جزیره گم‌شده به بنجامین لاینوس و عدم پذیرش رهبری توسط جک، افراد جزیره بر آن شدند تا رهبری جدید تعیین کنند و درخت ریاست را از نو رسم نمایند.

درخت ریاست درختی ریشه‌دار است، که رئوس آن متناظر با افراد جزیره است. در صورتی راس ‎$a$‎ پدر ‎$b$‎ است که در جزیره فرد متناظر با راس ‎$a$‎ رئیس ‎$b$‎ باشد، و در این صورت ‎$b$‎ را زیردست ‎$a$‎ می‌نامیم. هر فرد حداکثر یک بار در درخت ریاست می‌آید. ممکن است بعضی افراد اصلاً در درخت ریاست ظاهر نشوند. هر فردی که در درخت آمده است، دقیقاً یک پدر دارد (به جز ریشه‌ی درخت).

اما بازسازی درخت ریاست به این سادگی نیست چون هر کسی حاضر نیست زیردست همه کار کند. هر کس حاضر است فقط از بعضی دوستان خودش دستور بگیرد. ضمناً بعضی افراد جزیره مشکوک به دست داشتن در قتل جان لاک هستند. هیچ فرد مشکوکی نباید زیردست یک فرد فرد مشکوک دیگر شود. هم‌چنین زیردستان یک فرد مشکوک، خود نباید هیچ زیردستی داشته باشند.

می‌خواهیم بیش‌ترین افراد در درخت ریاست قرار بگیرند تا کارها سریع‌تر راه بیفتد. با گرفتن رابطه‌های فرمان‌برداری میان افراد و هم‌چنین افراد مشکوک، اندازه‌ی بزرگ‌ترین درخت ریاست ممکن را بیابید.

ورودی

  • در سطر اول ورودی ‎$n$‎، ‎$m$‎ و ‎$k$‎ آمده است. ‎$n$‎ تعداد آدم‌های جزیره است.
  • در ‎$m$‎ سطر بعدی در هر سطر یک جفت ‎$u$‎ و ‎$v$‎ آمده است که نشان می‌دهد که ‎$u$‎ می‌تواند زیردست ‎$v$‎ کار کند.
  • سطر آخر ورودی شامل ‎$k$‎ عدد است که شماره‌ی افراد مشکوک جزیره می‌باشند.
  • $1 \le n \le 1000$‎ و ‎$0 \le k \le n$‎
  • ‎$1 \le m \le 50000$‎

خروجی

تعداد رئوس بزرگ‌ترین درخت ریاست را در یک خط بنویسید.

محدودیت‌ها

  • محدودیت زمان: ۱ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

ورودی و خروجی نمونه

ورودی نمونه خروجی نمونه
6 8 1‎
1 3‎
3 4
‎4 3‎
4 2‎
2 1‎
6 4‎
4 5‎
5 6‎
4
5

ابزار صفحه