فهرست مندرجات
مهره‌های پرتحرک
گراف جهت‌دار بی‌دورDAG) $G$) به شما داده شده است. در ثانیه‌ی صفر روی هر کدام از رئوس این گراف تعدادی مهره قرار گرفته است. در هر لحظه برای هر کدام از رئوس گراف عمل زیر صورت می‌گیرد:
درصورتی که تعداد مهره‌های روی آن رأس، کمتر از درجه‌ی خروجی‌اش نباشد، آن رأس به هر کدام از رأس‌هایی که به آن‌ها یال دارد، یکی از مهره‌هایش را می‌دهد.
دقت کنید که این عمل در هر ثانیه به‌طور هم‌زمان روی همه‌ی رئوس گراف $G$ انجام می‌شود. به عبارت دیگر ممکن است در یک ثانیه رأس $v$ به رأس‌هایی که به آن‌ها یال می‌دهد مهره بدهد و از رأس‌هایی که به او یال دارند مهره دریافت کند. بدیهی است که اگر درجه‌ی خروجی راس $v$ صفر باشد، هیچ گاه مهره‌ای از آن خارج نمی‌شود.
می‌توان ثابت کرد که با انجام این عمل به تعداد زیاد سرانجام لحظه‌ای فرا می‌رسد که هیچ مهره‌ای حرکت نمی‌کند؛ این زمان) که زودترین ثانیه‌ای است که در آن هیچ مهره‌ای جابه‌جا نمی‌شود) را لحظه‌ی نهایی می‌نامیم.
برنامه‌ای بنویسید که گراف $G$ و تعداد مهره‌هایی که در ثانیه‌ی صفر در هر رأس آن وجود دارد را بخواند و تعداد مهره‌های موجود در هر رأس را در لحظه‌ی نهایی بنویسد.
ورودی
- در سطر نخست ورودی ابتدا عدد$n$، تعداد رئوس گراف $G$ و سپس عدد $e$، تعداد یال‌های گراف آمده است.
- در $n$ سطر بعدی در هر سطر یک عدد آمده است به‌طوری که عدد موجود در سطر $i+1$اُم، تعداد مهره‌هایی است که در حالت اوّلیه در رأس $i$اُم گراف $G$ قرار دارند.
- در $e$ سطر بعدی در هر سطر به‌ترتیب دو عدد $x$ و $y$ آمده است که نشان‌دهنده‌ی یک یال جهت‌دار از رأس $x$ به رأس $y$ است.
- $1 \leq n \leq 50,000$.
- $1\leq e\leq 200,000$.
- می‌توانید فرض کنید که به ازای هر زوج مرتّب $(x,y)$ حداکثر یک یال جهت‌دار از $x$ به $y$ وجود دارد.
- مجموع تعداد مهره‌هایی که روی رئوس گراف قرار دارد کمتر از $2^{31}$ است.
خروجي
در تنها سطر فایل خروجی شما بایستی $n$ عدد بنویسید بطوری که عدد $i$اُم موجود در این سطر نشان‌دهنده‌ی تعداد مهره‌هایی است که در لحظه‌ی نهایی در رأس $i$اُم گراف قرار خواهند داشت. اعداد را با فاصله‌ی خالی از هم جدا کنید.
محدودیت‌ها
- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
ورودي و خروجي نمونه
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
