+ محدودیت زمان: ۳ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- علی که دانش‌جویی دغدغه‌مند است تصمیم گرفته کاری جهادی به انجام برساند و شبکه‌ی ملی مواسات را راه‌اندازی کرده‌ست. این شبکه با متصل کردن خیرین شهرهای مختلف به یک‌دیگر ضمن نیازسنجی از هر منطقه کمک می‌کند خیرین شهر دارای تقاضا از خیرین دیگر شهرها تقاضای کمک کنند. این شبکه از پیوندهایی تشکیل شده است که هر پیوند دو خیّر را به هم متصل می‌کند. پارسا که دانش‌جویی ظاهرالصلاح است، با دانش اندک خود از شبکه و امنیت قصد خراب‌کاری دارد. او تصمیم دارد یکی از پیوندها را مختل کند. بین پیوندهای موجود او پیوندی را انتخاب می‌کند که بیشترین آسیب را به شبکه‌ی مواسات بزند؛ یعنی بیشینه تعداد جفت از خیّرها را از هم جدا کند. منظور از جدا شدن دو خیر این است که پیش از آن با شبکه‌ی پیوندها به هم متصل بوده‌ند و پس از حمله‌ی پارسا دیگر متصل نیستند. مهدی که دانش‌جویی دغدغه‌مند، پرکار و باطن‌الصلاح است با یک یاعلی وارد میدان شده و قصد دارد پیش از حمله‌ی پارسا (که اتفاقاً از دوستان قدیمی خودش است) حداکثر $k$ پیوند دیگر در شبکه ایجاد کند. به شبکه‌ی مواسات کمک کنید تا دریابد اگر مهدی بهترین پیوندهای ممکن را ایجاد کند پس از حمله‌ی پارسا چند جفت جدید از خیرین از هم جدا می‌شوند. # ورودی خط اول ورودی شامل $n, m, k$ است، تعداد خیرین، تعداد پیوندها و تعداد پیوندهایی که مهدی می‌تواند ایجاد کند. در $m$ خط بعدی پیوندها به شکل $v u$ داده می‌شوند. $$0 \le n, m, k \le 300\ 000$$ $$1 \le v, u \le n$$ # خروجی تعداد خیرینی که بعد از هم جدا می‌شوند، در صورتی که مهدی بهینه عمل کند. # مثال ## ورودی نمونه ۱ ``` 3 3 1 1 2 2 3 1 3 ``` ## خروجی نمونه ۱ ``` 0 ``` پارسا هیچ کاری نمی‌تواند بکند. ## ورودی نمونه ۲ ``` 7 6 1 1 2 2 3 3 4 3 5 5 6 5 7 ``` ## خروجی نمونه ۲ ``` 6 ```

حل سؤال در بانک سؤالات