Сізге $n$ төбеден және $m$ қабырғадан тұратын бағытталмаған граф берілген. Төбелер нөлден бастап нөмірленген: $0, 1, \dots, n - 1$. Сізге $q$ сұранымды өңдеу қажет. Әрбір сұраным $(u, v)$ жұбын береді және графтан $(u, v)$ қабырғасын өшіруді сұрайды. Егер графта мұндай қабырға болмаса (мысалы, егер $u = v$ болса), ештеңе істемеңіз. Әрбір сұранымнан кейін графтың байланысқан немесе байланыспаған екенін шығарыңыз.
Кіріс деректері
Кіріс деректері бірнеше тест жиынтығынан тұрады. Бірінші жолда бір бүтін сан $t$ ($1 \le t \le 5 \cdot 10^5$) — тест жиынтықтарының саны берілген. Одан кейін тест жиынтықтарының сипаттамасы беріледі.
Әрбір тест жиынтығының бірінші жолында үш бүтін сан $n$, $m$ және $q$ ($2 \le n \le 10^6$, $1 \le m, q \le 10^6$) берілген: сәйкесінше төбелер, қабырғалар және сұранымдар саны.
Келесі $m$ жолдың әрқайсысында $u_i$ мен $v_i$ арасындағы қабырғаны білдіретін екі бүтін сан $u_i$ және $v_i$ ($0 \le u_i, v_i < n$) берілген. Графта ілмектер мен еселі қабырғалар жоқ.
Келесі $q$ жолдың әрқайсысы бір сұранымды сипаттайды. Алайда сұраным параметрлері $u_j$ мен $v_j$ тікелей берілмейді. Оның орнына осы жолдардың $j$-шісінде екі бүтін сан $a_j$ және $b_j$ ($0 \le a_j, b_j < n$) берілген. $k$-шы сұранымның жауабы граф байланысқан болса $c_k = 1$, әйтпесе $c_k = 0$ болсын делік. Сонда $u_j$ мен $v_j$ келесі формулалар бойынша есептеледі:
$$u_j = (2^{j-2}c_1 + 2^{j-3}c_2 + \dots + 2^1 c_{j-2} + 2^0 c_{j-1} + a_j) \bmod n,$$
$$v_j = (3^{j-2}c_1 + 3^{j-3}c_2 + \dots + 3^1 c_{j-2} + 3^0 c_{j-1} + b_j) \bmod n.$$
Барлық тест жиынтықтары бойынша барлық $n$ қосындысы, барлық $m$ қосындысы және барлық $q$ қосындысы $10^6$-нен аспайды.
Шығыс деректері
Әрбір тест жиынтығы үшін сұранымдардың жауаптары болатын $c_1, \dots, c_q$ бүтін сандары бар $q$ жол шығарыңыз.
Мысал
Кіріс мысалы 1
2 3 1 2 0 1 0 0 0 1 4 4 4 0 1 1 2 2 3 0 3 0 1 1 3 0 0 2 3
Шығыс мысалы 1
0 0 1 1 0 0
Ескертпе
Бірінші тест жиынтығында сұранымдар $(0, 0)$ (ол жоқ) және $(0, 1)$ қабырғаларын өшіруді сұрайды.
Екінші тест жиынтығында сұранымдар $(0, 1)$, $(2, 0)$ (ол жоқ), $(3, 0)$ және $(0, 3)$ (ол алдыңғы амалмен өшіріліп қойған) қабырғаларын өшіруді сұрайды.