Олимпиадный тренинг

Задача . D. Мгновенные сообщения


Задача

Темы: Структуры данных

Пользователь ainta решил запустить новую систему мгновенных сообщений под названием «aintalk». Используя aintalk, каждый пользователь может беседовать с другими. Пользователь ainta создал прототипы некоторых функций для реализации этой системы.

  1. login(u): Пользователь u заходит в aintalk и становится online.
  2. logout(u): Пользователь u выходит и становится offline.
  3. add_friend(u, v): Пользователь u и пользователь v становятся друзьями. Это значит, что u и v могут разговаривать друг с другом. Отношение дружбы симметричное.
  4. del_friend(u, v): Пользователи u и v прекращают дружбу. Это значит, что u и v с этого момента не могут разговаривать друг с другом.
  5. count_online_friends(u): Функция возвращает количество друзей пользователя u, которые на текущий момент online.
 

Пользователь ainta реализовал описанные функции, но до того, как выпустить релиз системы, он хочет удостовериться, что его код правильный. Помогите ainta проверить код, промоделируйте работу его функций.

Так как сейчас сервер сообщений тестируется некоторыми пользователями, пронумерованными от 1 до n, нет метода, реализующего регистрацию. В момент начала проверки кода некоторые пользователи могут быть online, и у некоторых пользователей могут быть друзья.

Входные данные

В первой строке записано три целых числа через пробел n, m и q (1 ≤ n ≤ 50000; 1 ≤ m ≤ 150000; 1 ≤ q ≤ 250000) — количество пользователей, количество пар друзей, и количество запросов.

Вторая строка содержит целое число o (1 ≤ o ≤ n) — количество онлайн-юзеров перед началом моделирования. В третьей строке записано o целых чисел через пробел x1, x2, ..., xo (1 ≤ xi ≤ n) — идентификаторы онлайн-юзеров. Гарантируется, что эти значения различны.

Каждая из следующих m строк содержит два целых числа через пробел, ai и bi (1 ≤ ai, bi ≤ n; ai ≠ bi) — идентификаторы двух пользователей, которые уже дружат перед началом моделирования. Гарантируется, что во входных данных не записано кратных дружеских связей. Обратите внимание, что дружба — двусторонняя связь.

Следующие q строк описывают q запросов в следующем формате:

  • «O u» (1 ≤ u ≤ n) : Вызов online(u). Гарантируется, что пользователь u был offline непосредственно перед вызовом функции.
  • «F u» (1 ≤ u ≤ n) : Вызов offline(u). Гарантируется, что пользователь u был online непосредственно перед вызовом функции.
  • «A u v» (1 ≤ u, v ≤ n; u ≠ v) : Вызов add_friend(u, v). Гарантируется, что эти два пользователя не были друзьями непосредственно перед вызовом функции.
  • «D u v» (1 ≤ u, v ≤ n; u ≠ v) : Вызов del_friend(u, v). Гарантируется, что эти два пользователя были друзьями непосредственно перед вызовом функции.
  • «C u» (1 ≤ u ≤ n) : Вызов count_online_friends(u) и вывод результата в единственной строке.
Выходные данные

Для каждого запроса count_online_friends(u), выведите необходимый ответ в единственной строке.


Примеры
№Входные данныеВыходные данные
1 5 2 9
1
4
1 3
3 4
C 3
A 2 5
O 1
D 1 3
A 1 2
A 4 2
C 2
F 4
C 2 
1
2
1

time 2000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w645
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет