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

خانج شخصیتی تپل‌ (شما بخوانید تو‌پر) و کم حاشیه است! او به تازگی تصمیم گرفته رژیم بگیرد و معمولا به رژیم خود پایبند است.

خانج تنها زمانی که درختی ببیند که رئوس آن رنگ شده اند، کنترل خود را از دست می‌دهد، و اگر در درخت بیشینه‌ی فاصله‌ی بین دو راس ناهمرنگ $x$ باشد، او $x$ جوس شیرینی خواهد خورد.(جوس یک واحد اندازه‌گیری شیرینی است که با توجه به وقت محدود امتحان به توضیح آن نمی‌پردازیم)

درختی داریم با $n$ راس و $k$ رنگ، رنگ بعضی از رئوس را نمی‌دانیم، رنگ آنها با عدد $0$ نشان داده شده و رنگ بقیه رئوس با اعداد $1$ تا $k$. از آنجا که ما به شدت نگران وضعیت رژیم خانج هستیم به دنبال آن هستیم که او با دیدن این درخت کمترین مقدار شیرینی را بخورد. پس تلاش می‌کنیم رئوسی که رنگشان معلوم نیست را طوری با رنگ‌های $1$ تا $k$ رنگ کنیم که رنگ $i$ام $a_{i}$ بار ظاهر شود و بیشینه‌ی فاصله‌ی میان $2$ راس ناهمرنگ کمینه شود. تضمین می‌شود که جمع رنگ‌ها $n$ است.

همچنین $q$ بار یک راس انتخاب شده، و رنگ آن تغییر می‌کند، به این صورت که اگر رنگش $1$ تا $k$ باشد٬ رنگ آن $0$ می‌شود(بی‌رنگ می‌شود) و اگر بی‌رنگ باشد رنگ آن به عددی از $1$ تا $k$ تبدیل می‌شود(تضمین می‌شود بعد از این عمل هیچ رنگ $i$ای بیش از $a_{i}$ بار ظاهر نخواهد شد)

از شما خواسته شده $q + 1$ عدد چاپ کنید، که نشان‌دهنده‌ی این است که در ابتدا و بعد از هر تغییر در درخت، خانج حداقل چند جوس شیرینی خواهد خورد؟

ورودی🔗

در سطر اول ورودی دو عدد $n$ و $k$ آمده‌است.

در $n - 1$ سطر بعد هر خط، دو عدد $u$ و $v$ آمده است، که به معنی وجود یالی از راس $u$ به راس $v$ می‌باشد.

در سطر بعدی $k$ عدد آمده است که عدد $i$ام برابر با $a_{i}$ است.

در سطر بعدی عدد $q$ آمده است.

در $q$ سطر بعدی، هر سطر $2$ عدد $x$ و $c$ آمده است، که به معنی تغییر رنگ راس $x$ به رنگ $c$ می‌باشد. اگر $c = 0$ باشد، به این معنا‌ست که این راس بی‌رنگ شود.

$1 \le n, k, q \le 100\ 000$ $1 \le u, v, x \le n$ $0 \le c \le k$

خروجی🔗

در $q + 1$ سطر خروجی، مقدار‌های گفته شده در صورت سوال را به ترتیب چاپ کنید.

زیر مسئله‌ها🔗

ورودی نمونه🔗

3 2
1 2
2 3
2 1
4
1 1
2 1
2 0
2 2

خروجی نمونه🔗

1
1
2
1
1

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

روزی دانش‌پژوهی از دانش‌پژوهان المپیاد کامپیوتر، در حرکتی اعتراضی به طرّاحی از طرّاحان خفن سوالات می‌گوید: «هیچکدومتون سوال طرح نمی‌کنید، همش می‌رید از یه جای ناشناخته سوال برمی‌دارید، می‌دید!»

طراح خفن در لحظه سوال زیر را طرح کرده و به دانش‌پژوه می‌دهد تا حقّانیّت خود را ثابت کند.

آرایه‌ای به نام $a$ به طول $n$ داریم، تعداد سه تایی‌های $1 < x < y < z < n$ را می‌خواهیم به طوری که $a_{z} < a_{x} < a_{y}$ باشد.

دانش‌پژوه که از کرده‌ی خود پشیمان است از شما کمک می‌خواهد تا این مقدار را بدست آورید.

ورودی🔗

در سطر اول ورودی عدد $n$ آمده‌است. در سطر بعدی $n$ عدد آمده است که عدد $i$ام برابر با $a_{i}$ است. $1 \le n \le 300\ 000$ $1 \le a_{i} \le 10^{9}$

خروجی🔗

در تنها سطر خروجی، مقدار گفته شده در صورت سوال را چاپ کنید.

زیر مسئله‌ها🔗

ورودی نمونه ۱🔗

3
2 3 1

خروجی نمونه ۱🔗

1

ورودی نمونه ۲🔗

7
1 3 3 4 4 2 2

خروجی نمونه ۲🔗

8

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

شایان مقادیر زیادی به بهنود بدهکار است.(مقدار زیادی وجه نقد، زمین‌های شمال مکزیک و بخش قابل توجهی از نفت خاورمیانه) و به همین علت تمام تلاشش را می‌کند تا با او مواجه نشود.

آن‌ها در شهری زندگی می‌کنند که به شکل یک گراف $n$ راسی و $m$ یالی است. شایان در ابتدا در راس $S$ است و می‌خواهد به راس $T$ که حمیدرضا در آنجا انتظارش را می‌کشد برود تا با او تنیس بازی کند(حمیدرضا خیلی اهل فوتبال نیست)

همزمان که شایان به سمت راس $T$ می‌رود، بهنود نیز که از اینکه نتوانسته طلبش را وصول کند، افسرده و پریشان شده با سرعتی برابر شایان گشتی مشخّص را با هدفی نامشخص طی می‌کند.(هر دو همزمان شروع به حرکت می‌کنند و برایشان طی کردن هر یال ۱ ثانیه زمان می‌برد) شایان کاملا مسیری که بهنود طی می‌کند را می‌داند، و سعی می‌کند گشتی را انتخاب کند که در هیچ کجای آن بهنود را نبیند٬ همچنین شایان می‌تواند در ۱ ثانیه در یک راس ثابت بماند و حرکت نکند یا در یک راس چند بار برود اما مسیر بهنود کاملا ساده است. (دقت کنید که شایان ممکن است بهنود را در یک راس یا در یک یال ببیند، در صورتی که هر دو همزمان در حال طی کردن آن یال باشند.)

او منطقا کوتاه‌ترین گشتی از $S$ به $T$ که شرط بالا را دارد طی می‌کند، اما قبل از حرکت از شما می‌خواهد که به او بگویید، طول این گشت چقدر است یا بگویید چنین گشتی وجود ندارد.

ورودی🔗

در سطر اول ورودی دو عدد $n$ و $m$ و در سطر بعد دو عدد $S$ و $T$ آمده‌است.

در $m$ سطر بعد هر خط، دو عدد $u$ و $v$ آمده است، که به معنی وجود یالی بی جهت از راس $u$ به راس $v$ می‌باشد.

در سطر بعدی عدد $k$ و در ادامه $k$ عدد آمده است که عدد $i$ام برابر با راس $i$ام مسیر بهنود است.

$1 \le n, m \le 1\ 000\ 000$ $1 \le s, t, u, v, k \le n$ $1 \le u , v \le n$

• تضمین می‌شود گراف ساده است.

خروجی🔗

در تنها سطر خروجی، طول کوتاه ترین گشت با شرط گفته شده در صورت سوال را چاپ کنید. اگر چنین گشتی وجود ندارد، -1‍ چاپ کنید.

زیر مسئله‌ها🔗

ورودی نمونه🔗

3 3
1 3
1 2
2 3
3 1
2
3 1

خروجی نمونه🔗

2