eolymp
bolt
Try our new interface for solving problems
Problems

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

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

Time limit 2 seconds
Memory limit 64 MiB

Винни-Пух зарегистрировался в новой социальной сети, которая называется ВЛесу. В этой социальной сети у каждого пользователя, кроме списка его друзей, был также список его врагов. В этот список можно было добавить любого пользователя, но при этом удовлетворялись некоторые условия:

  1. Если пользователь v является врагом пользователя u, то uне обязательно является врагом v.

  2. Пользователь не может быть врагом самого себя.

Винни-Пуху очень понравилась эта социальная сеть. Он целыми днями сидел и записывал, кто же становился чьим врагом, так как хотел знать все, что происходит в их лесу. Он считал, что никто не пойдет в гости к своему врагу. Также, по его мнению, враг врага является другом, а любая уважающая своих друзей персона должна пойти в гости к своему другу. Винни-Пуху очень интересно узнать - сколько же у пользователя под номером v друзей. Пользователь u является другом пользователя v по версии Винни-Пуха, если выполняются некоторые условия:

  1. u является врагом некоторого врага v

  2. u не является врагом v

Заметим также, что никакой пользователь сам не является своим другом.

Input data

В первой строке входного файла задано числа n и m (1n, m2000) - количество пользователей, зарегистрированных в социальной сети и количество запросов соответственно.

В следующих m строках заданы запросы двух видов:

  1. + v u - пользователь v начал считать пользователя u своим врагом

  2. ? v - узнать количество друзей пользователя v по версии Винни-Пуха

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

Output data

Для каждого запроса ? v выведите одно целое число - ответ на него в отдельной строке.

Examples

Input example #1
5 5
+ 1 2
+ 2 4
+ 2 5
+ 1 5
? 1

Output example #1
1
Author Нияз Нигматуллин