- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
گراف \(G\) یک گراف ساده و بدون جهت است. \(G\) شامل \(n\) راس و \(m\) یال است. فرض کنید یالهای \(G\) به ترتیب ورودی مسئله
\[e_1, e_2, e_3, \dots, e_m\]
باشند.
از شما میخواهیم برای \(q\) بازه \(l_i\) و \(r_i\) بررسی کنید آیا اجتماع یالهای این بازه تشکیل یک زیردرخت برای \(G\) میدهد یا نه. به عبارت دیگر اجتماع \[e_{l_i}, e_{l_i + 1}, e_{l_i + 2}, \dots, e_{r_i}\] تشکیل یک زیردرخت برای \(G\) میدهد یا نه.
توجه کنید یک زیردرخت از \(G\) یک زیرمجموعه از یالهای \(G\) است که تشکیل یک گراف همبند بدون دور را بدهد. (نیازی نیست که این زیردرخت فراگیر باشد و شامل همه راسهای \(G\) باشد.)
ورودی
در سطر اول ورودی دو عدد صحیح و مثبت \(n\) و \(m\) با یک فاصله آمده است که به ترتیب نشاندهنده تعداد راسها و تعداد یالهای گراف است.
\[2 \le n \le 100 \, 000 \quad\quad 1 \le m \le 100 \, 000\]
در \(m\) سطر بعدی در هر سطر دو عدد صحیح و مثبت \(u_i\) و \(v_i\) با یک فاصله آمده است که نشاندهندهی یال \(i\)ام گراف یعنی \(e_i\) است.
\[1 \le u_i \neq v_i \le n\]
تضمین میشود هیچ یالی دوبار ورودی داده نمیشود و گراف داده شده در ورودی یک گراف ساده (نه لزوماً همبند) خواهد بود.
در سطر بعدی تنها یک عدد صحیح و مثبت \(q\) آمده است که تعداد سوالاتی را نشان میدهد.
\[1 \le q \le 100 \, 000\]
در \(q\) سطر بعدی در هر سطر دو عدد صحیح و مثبت \(l_i\) و \(r_i\) آمده است که بازه مورد نظر در سوال \(i\)ام را نشان میدهد.
\[1 \le l_i \le r_i \le m\]
خروجی
خروجی شامل \(q\) سطر است و در سطر \(i\)ام آن اگر زیرگراف متناظر با بازهی \(i\)ام مورد سوال، درخت بود کلمه YES و در غیر این صورت کلمه NO را چاپ کنید.
مثال
ورودی نمونه ۱
3 3
1 2
1 3
2 3
6
1 1
1 2
1 3
2 2
2 3
3 3
خروجی نمونه ۱
YES
YES
NO
YES
YES
YES
ورودی نمونه ۲
5 5
1 2
3 4
2 3
4 5
5 1
4
1 2
1 3
1 4
1 5
خروجی نمونه ۲
NO
YES
YES
NO