print2083. Враг моего врага - мой друг!

printВраг моего врага - мой друг!

Ограничения: время – 2s/4s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Винни-Пух зарегистрировался в новой социальной сети, которая называется ВЛесу. В этой социальной сети у каждого пользователя, кроме списка его друзей, был также список его врагов. В этот список можно было добавить любого пользователя, но при этом удовлетворялись некоторые условия:
Если пользователь `v` является врагом пользователя `u`, то `u` не обязательно является врагом `v`
Пользователь не может быть врагом самого себя
Винни-Пуху очень понравилась эта социальная сеть. Он целыми днями сидел и записывал, кто же становился чьим врагом, так как хотел знать все, что происходит в их лесу. Он считал, что никто не пойдет в гости к своему врагу. Также, по его мнению, враг врага является другом, а любая уважающая своих друзей персона должна пойти в гости к своему другу. Винни-Пуху очень интересно узнать – сколько же у пользователя под номером `v` друзей. Пользователь `u` является другом пользователя `v` по версии Винни-Пуха, если выполняются некоторые условия:
  • `u` является врагом некоторого врага `v`
  • `u` не является врагом `v`
Заметим также, что никакой пользователь сам не является своим другом.
В первой строке входного файла задано числа `n` и `m` (`1\ ≤\ n`, `m\ ≤\ 2\ 000`) – количество пользователей, зарегистрированных в социальной сети и количество запросов соответственно.
В следующих `m` строках заданы запросы двух видов:
  • + `v` `u`  – пользователь `v` начал считать пользователя `u` своим врагом
  • ? `v`  – узнать количество друзей пользователя `v` по версии Винни-Пуха
Гарантируется, что входные данные корректны – пользователь не начнет считать себя своим врагом и никакой пользователь не станет врагом другого более одного раза.
Для каждого запроса ? `v` выведите одно целое число – ответ на него в отдельной строке.

Пример ввода

5 5
+ 1 2
+ 2 4
+ 2 5
+ 1 5
? 1

Пример вывода

1
Источник: neerc.ifmo.ru/school
loading