Республиканская олимпиада по информатике, 2011 год, 10-11 классы

Есеп F. Сайлау

Ограничение по времени:

2 секунды

Ограничение по памяти:

256 мегабайта

Қалада $N$ қиылыстар және $M$ көшелер бар. Кез келген қиылыстан басқа қиылысқа жетуге болады және ол жол жалғыз. Қаланың әкiмi болу үшiн күрес басталды. Сайлаудың ақтық мәресiне екi кандидат шықты. Сайлау алдындағы үгiт көшелерде болады. Әр көшеде нақты бiр кандидатқа сайлау алдындағы үгiттi жүргiзетiн адамдар бар.

Формат входного файла

Енгiзу файлдың бiрiншi жолында екi бүтiн сандар $N$ және $M$ берiлген $(1 \le N, M \le 10^5).$ Келесi $M$ жолдардың әрқайсысында қаланың сипаттамасы $a$ және $b$ — осы көше қосатын қиылыстар $(1 \le a, b \le N).$ Келесi жолда сұраулардың саны — $K$ берiледi $(1 \le K \le 10^5).$ Келесi $K$ жолдарда сұрау лар берiлген. Сұраудың екi түрлерi бар:
$+$ $x$ $y$ — $x$-шi кандитат $y$-шi көшесiнiң дауысын өзгерттi, және ендi $y$-шi көше оған сайлау алдындығы үгiттi жүргiзедi $(1 \le x \le 2,$ $1 \le y \le M).$
$q$ $x$ $y$ $k$ — $x$ және $y$ көшелерiнiң арасында $k$-шi кандидатқа қанша көше сайлау алдындағы үгiттi жүргiзедi $(1 \le k \le 2).$ Басында барлық көшелер 1-шi кандидатқа сайлау алдындағы үгiттi жүргiзедi

Формат выходного файла

Әр екiншi типтi сұрауға (жоғарыда берiлген) жауап шығарыңыз.

Примеры:

Вход

3 2
1 2
1 3
3
q 1 3 1
+ 2 1
q 1 3 1

Ответ

2
1