Задача №114809. Реактивные поезда
3019 год. Всё человечество давно живёт в городах, парящих в атмосфере на аэростатах и реактивных двигателях. На планете есть \(n\) городов, между некоторыми парами городов курсируют реактивные поезда. Если между городами \(a\) и \(b\) курсируют реактивные поезда, то пассажиры могут перемещаться между этими городами в любом направлении. Будем говорить, что из города \(a\) достижим город \(b\), если пассажир может добраться от \(a\) до \(b\) с использованием реактивных поездов, возможно с пересадками.
Люди в 3019 любят дружить, и дружат не парами, а целыми городами. Отношение дружбы взаимно: если город \(a\) дружит с городом \(b\), то город \(b\) также дружит с городом \(a\).
Время от времени в каком-нибудь городе решают организовать праздник и зовут всех своих друзей к себе в гости. Если праздник проходит в городе \(a\), то гости из всех городов, которые дружат с \(a\), и из которых достижим город \(a\), прибывают на мероприятие, пользуясь реактивными поездами.
Для того, чтобы оценивать количество гостей на празднике, решено было разработать специальную информационную систему «Праздник 3019». Задан список текущих рейсов реактивных поездов, а также информация о том, какие города дружат. Информационная система должна обрабатывать запросы вида: «Если в городе \(v\) случится праздник, гости из скольки городов попадут на него?» Кроме того, должна поддерживаться возможность добавить информацию о новом рейсе реактивного поезда, а также о новой паре городов, которые начинают дружить. К счастью, рейсы не отменяются, и однажды подружившись, города навсегда остаются друзьями.
Помогите человечеству разработь описанную информационную систему.
В первой строке заданы три целых числа \(n\), \(m\) и \(k\) — количество городов, пар исходно дружащих городов и рейсов реактивных поездов (\(1 \le n \le 10^5\), \(0 \le m, k \le 10^5\)).
В следующих \(m\) строках находятся по два целых числа \(a\), \(b\) (\(1 \le a, b \le n\), \(a \neq b\)) — пары дружащих городов. Каждая пара дружащих городов указана во вводе ровно один раз.
В следующих \(k\) строках находятся по два целых числа \(a\), \(b\) (\(1 \le a, b \le n\), \(a \neq b\)) — пары городов, соединённых рейсами реактивных поездов. Каждая пара городов соединена не более, чем одним рейсом.
Следующая строка содержит число \(q\) (\(0 \le q \le 10^5\)) — количество запросов, которые следует обработать, а в следующих \(q\) строках заданы сами запросы.
- Запрос « T \(a\) \(b\)» означает, что между городами \(a\) и \(b\) запущен рейс реактивного поезда (\(1 \le a, b \le n\), \(a \neq b\)). Гарантируется, что до этого запроса между этими городами рейса не было.
- Запрос « F \(a\) \(b\)» означает, что города \(a\) и \(b\) начинают дружить (\(1 \le a, b \le n\), \(a \neq b\)). Гарантируется, что до этого запроса эти города не дружили.
- Запрос « ? \(v\)» означает, что к информационной системе сделан запрос: «Если в городе \(v\) случится праздник, гости из скольки городов попадут на него?» (\(1 \le v \le n\))
Для каждого запроса « ? \(v\)» выведите ответ на него в отдельной строке.
Ответ на первый запрос равен единице, потому что только один из городов \({2, 3}\) соединен с городом \(1\) рейсом поездов. Ответ на второй запрос равен двойке, потому что перед этим города \(1\) и \(4\) подружились, а они были соединены рейсом напрямую. Ответ на третий вопрос равен тройке, потому что от города \(3\) стало возможным добраться на поездах до города \(1\) следующим образом: сначала доехать до города \(4\), а потом от него до города \(1\).
4 2 2 1 2 1 3 1 2 1 4 5 ? 1 F 4 1 ? 1 T 4 3 ? 1
1 2 3