قیمت نفت در بازارهای بورس تابع فاکتورهای زیادی است. یکی از این فاکتورها «چشم و هم چشمی» میان کمپانی‌ها و کشورهای فعّال در بورس است! برای مثال ممکن‌ست کشور بلیز (یکی از کشورهای آمریکای لاتین که جمعیتش کمی بیش‌تر از باشگاه دانش‌پژوهان جوان است!) به‌تنهایی حاضر باشد نفت دریای شمال را حداکثر به‌قیمت بشکه‌ای ۸۰ دلار بخرد اما وقتی ببیند مثلاً ونزوئلا، اوگاندا، جزایر قناری، ساحل عاج و زامبیا (که مثلاً رقیب‌های اقتصادی بلیز است!) دارند نفت می‌خرد، حاضر می‌شود تا ۸۵ دلار هم برای هر بشکه نفت بدهد. در سوی دیگر، کشورهای نفت‌خیز که فروشنده‌ی نفت هستند و از رقابت‌های اقتصادی میان کشورها خبر دارند، دوست دارند حداکثر فروش با سود مناسب را کرده و سود زیادی را در این میان به‌دست بیاورند.

آقای «زی» (که اکسیر جوانی‌اش را نتوانست بسازد اما چیز دیگری ساخت و به خورد آقای «کا» داد و با قایق او فرار کرد(! مشاور اقتصادی یک کمپانی بزرگ فروشنده‌ی نفت است. یک روز صبح رئیس کمپانی از او خواست تا با دانستن روابط اقتصادی میان کشورهای خریدار نفت و حداکثر «ارزش اوّلیه‌ی نفت» (حداکثر پولی که آن کشور حاضرست در ابتدای کار و پیش از «چشم و هم‌چشمی»ها برای نفت بپردازد) تک‌تک کشورها، یک قیمت ثابت و کلّی برای فروش نفت تعیین کند.

آقای «زی» می‌داند که هرگاه کشور $X$ اقدام به خرید نفت کند، ارزش نفت در نزد هر کدام از کشورهایی که با $X$ رقابت دارند و هنوز نفت نخریده‌اند، یک دلار افزایش می‌یابد. هم‌چنین هر کشور حداکثر یک‌بار اقدام به خرید نفت می‌کند و کشوری که ارزش نفت (که با خرید نفت توسّط رقبایش افزایش می‌یابد) برایش بیش‌تر یا مساوی قیمت نفت (که همواره ثابت است) بشود، در صورتی که هنوز نفت نخریده باشد، بلافاصله اقدام به‌خرید نفت می‌کند.

طبق اطلاعات داده شده به آقای «زی»، در صورتی که قیمت نفت برابر $V$ دلار باشد و در پایان کار $n$ کشور نفت بخرند، سود نهایی کمپانی برابر $nV$ می‌شود.

به آقای «زی» کمک کنید و برنامه‌ای بنویسید تا با دریافت ارزش اوّلیه‌ی نفت کشورها و رقابت‌های اقتصادی بین‌شان، قیمت نفت را طوری تعیین کند که بیش‌ترین سود عاید کمپانی بشود.

• در سطر اوّل ورودی، $n$، تعداد کشورها، آمده است.
• در سطر دوم $n$ عدد آمده است که عدد $1\le i \le n$ (از سمت چپ) ارزش اوّلیه نفت در نزد کشور $i$ را نشان می‌دهد.
• در سطر سوم $e$ تعداد روابط رقابتی آمده است.
• در سطر‌های چهارم تا $e+3$،اُم در هر سطر دو عدد $X$ و سپس $Y$ آمده است که حضور $X~Y$ به این معنی‌است که $X$ (عدد سمت چپ) چشم به $Y$ دوخته است و اگر $Y$ نفت بخرد، ارزش نفت در نزد $X$ یک‌واحد افزایش می‌یابد. شماره کشورها از $1$ تا $n$ است.
• $0 \le e \le 5\times10^5$
• $1 \le n \le 10^5$، اما در ۸۰ درصد تست‌ها $n \le 1000$ و در ۳۰ درصد تست‌ها $n \le 100$ است.

در تنها سطر خروجی بهترین قیمت اوّلیه‌ی نفت را بنویسید که بیش‌ترین سود (حاصل‌ضرب قیمت‌اوّلیه در تعداد کل کشورهایی که نفت می‌خرند) را به کمپانی می‌رساند.

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