Masala B

Robolandiya mamlakati nihoyat tinimsiz janglardan so'ng ozodlikka erishdi. Endilikdagi maqsad mamlakatdagi barcha shaharlar orasida yo'l qurish. Mamlakatda $N$ ta shahar hamda hozircha bu shaharlarni bog’lovchi yo’llar umuman mavjud emas. Jami $M$ ta ikki tomonlama yo’llar qurish rejalashtirilgan. $u$ va $v$ shaharni bog’lovchi yo’l $(u, v)$ ko'rinishida ifodalanadi. Yo’l qurilish rejasi tayyor va unga ko’ra birinchi bo’lib $(u_1, v_1)$, ikkinchi bo’lib $(u_2, v_2)$… oxirgi bo’lib $(u_M, v_M)$ yo’li quriladi. Istalgan bir yo’lni qurish uchun 1 kun vaqt kerak.

$S$ to’plami mavjud va bu to’lam hozircha bo’sh.
Bu mamlakatga mehmonlar kelmoqchi. Mehmonlar rejasiga ko’ra ular $S$ to’plamdagi istalgan bir shahardan boshlab, qurilgan yo’llardan yurgan shu to’plamdagi barcha shaharlarni ko’rib chiqishmoqchi. Bunda ular sayohati davomida ba’zi shaharlarni bir necha marta aylanishsa yoki to'plamda bo'lmagan shaharlarga kirishsa ham mayli. Ularning butun sayohati vaqt olmaydi deb tasavur qiling!

Ikki xil turdagi $Q$ ta so’rovlar beriladi.
$+\ X$ so’rovi. $S$ to’plamiga $X$ - shaharni qo’shish (to’plamda oldin $X$ shahri yo’qligi kafolatlanadi)
$-\ X$ so’rovi. $S$ to’plamdan $X$ - shaharni o’chirish (to’plamda $X$ shahri borligi kafolatlanadi)

Har safar S to’plamga o’zgartirish kiritilganidan so’ng, agar yo’l qurilishi bugun boshlansa, kamida necha kundan so’ng ushbu sayohatchilar mamlakatga tashrif buyurishlari mumkinligini ayting.

Kirish faylida $N$ va $M$  sonlari beriladi $(1 \le N \le 10^5, 1 \le M \le 5 * 10^5)$.

Keyingi $M$ ta qatorning har birida ikkitadan butun son - $u_i$ va $v_i$ kiritiladi.$(1 \le i \le M, 1 \le u_i, v_i \le N, u_i \neq v_i)$. Barcha yo'llar qurilib bo'lganidan so'ng, hamma shaharlar bog'langan bo'lishi kafolatlanadi.

Keyingi qatorda bitta butun son - $Q(1 \leq Q \leq 4*10^5)$ so'rovlar soni kiritiladi.

Keyingi $Q$ ta qatorda so'rovlar kiritiladi.

Subtask #1: $M = N-1$; $X_i = i$; $Y_i = i+1$ (4 ball)

Subtask #2: $N \le 100$; $M, Q \leq 400$ (7 ball)

Subtask #3: $N \le 3000$; $Q \leq 6000$ (12 ball)

Subtask #4: $N, Q \le 4*10^4$, har qanday holatda $|S| \le 2$ (27 ball)

Subtask #5:  $Q \le 500$ (15 ball)

Subtask #6: Qo'shimcha cheklovlarsiz (35 ball)

Chiqish faylida har bir so'rov uchun alohida qatorda minimum necha kun kutish kerakligini chop eting. 

($S$ bo’sh bo’lsa $-1$ chiqaring, $S$ 1 ta elementdan tashkil topgan bo’lsa $0$ chiqaring)