سوال ۲

آقای مهندس می‌خواهد یک گراف «مهندسی‌ساز» بسازد. به یک گراف وزن‌دار مهندسی‌ساز می‌گوییم اگر بتوان طوری وزن تعدادی از یال‌هایش را مقدار مثبتی زیاد کرد که هیچ‌کدام از MSFهای گراف سابق در گراف جدید MSF نباشند. آقای مهندس در حال ساختن گرافش است و در هر مرحله یک یال جدید به آن اضافه می‌کند. شما باید در هر مرحله به او بگویید گرافش مهندسی‌ساز است یا نه.

به یک زیرگراف از گرافمان، جنگل فراگیر می‌گوییم اگر دور نداشته باشد و بین هر دو راسی که در درون یک مؤلفه قرار دارند، با یال‌های این زیرگراف مسیر وجود داشته باشد. به زیرجنگلی که جمع وزن‌ یال‌هایش کمینه باشد، Minimum Spanning Forest یا MSF می‌گوییم.

• در خط اول ورودی دو عدد $n$ و $m$ آمده‌اند که $n$ تعداد راس‌های گراف و $m$ تعداد یال‌های آن را نشان می‌دهد. در $m$ خط بعد در هر خط سه عدد $u_i$ و $v_i$ و $w_i$ آمده‌است که اضافه شدن یالی به وزن $w_i$ بین دو راس $u_i$ و $v_i$ را نشان می‌دهد. دقت کنید که یال‌ها ممکن است چندگانه باشند.
• $1 \leq n, m \leq 10^5$
• $1 \leq u_i, v_i ≤ n, 1 \leq w_i \leq 10^9$

در تنها خط خروجی یک رشته به طول $m$ از $0$ و $1$ چاپ کنید که $1$ بودن حرف $i$ام آن به معنی مهندسی‌ساز بودن گراف بعد از اضافه کردن یال $i$ام است.

• زیرمسئله اول (۱۰ نمره): وزن تمامی یال‌ها متفاوت است و $1 \leq n, m \leq 2000$
• زیرمسئله دوم (۳۵ نمره): $1 \leq n, m \leq 2000$
• زیرمسئله سوم (۵۵ نمره - بدون فیدبک): بدون محدودیت اضافی

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

• سوال بعد
• سوال قبل