- محدودیت زمان: ۲ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
- منبع: آزمون عملی دوره ۲۴ المپیاد کامپیوتر
آقای مهندس میخواهد یک گراف «مهندسیساز» بسازد. به یک گراف وزندار مهندسیساز میگوییم اگر بتوان طوری وزن تعدادی از یالهایش را مقدار مثبتی زیاد کرد که هیچکدام از MSFهای گراف سابق در گراف جدید MSF نباشند. آقای مهندس در حال ساختن گرافش است و در هر مرحله یک یال جدید به آن اضافه میکند. شما باید در هر مرحله به او بگویید گرافش مهندسیساز است یا نه.
به یک زیرگراف از گرافمان، جنگل فراگیر میگوییم اگر دور نداشته باشد و بین هر دو راسی که در درون یک مؤلفه قرار دارند، با یالهای این زیرگراف مسیر وجود داشته باشد. به زیرجنگلی که جمع وزن یالهایش کمینه باشد، Minimum Spanning Forest یا MSF میگوییم.
ورودی
در خط اول ورودی دو عدد \(n\) و \(m\) آمدهاند که \(n\) تعداد راسهای گراف و \(m\) تعداد یالهای آن را نشان میدهد. در \(m\) خط بعد در هر خط سه عدد \(u_i\) و \(v_i\) و \(w_i\) آمدهاست که اضافه شدن یالی به وزن \(w_i\) بین دو راس \(u_i\) و \(v_i\) را نشان میدهد. دقت کنید که یالها ممکن است چندگانه باشند.
\[1 \le n, m \le 100\ 000\] \[1 \le u_i, v_i \le n\] \[1 \le w_i \le 10^9\]
خروجی
در تنها خط خروجی یک رشته به طول \(m\) از 0 و 1 چاپ کنید که 1 بودن حرف \(i\)ام آن به معنی مهندسیساز بودن گراف بعد از اضافه کردن یال \(i\)ام است.
زیرمسئلهها
| زیرمسئله | نمره | محدودیت |
|---|---|---|
| ۱ | ۱۰ | \( n , m \le 2\ 000\) , وزن تمامی یال ها متفاوت است |
| ۲ | ۳۵ | \( n , m \le 2\ 000 \) |
| ۳ | ۵۵ | بدون محدودیت اضافی |
مثال
ورودی نمونه
6 7
1 2 2
1 3 2
3 2 2
5 6 1
3 5 1
1 4 1
1 5 1
خروجی نمونه
0000001
(۲۴امین دوره المپیاد کامپیوتر -آزمون یکم -۱۳۹۳/۰۵/۲۳)