Ворог мого ворога — мій друг!#2359

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

2 секунди

64 мегабайти

Дуже легка

Вінні-Пух приєднався до нової соціальної мережі під назвою InTheForest. У цій платформі кожен користувач має список друзів і список ворогів. Користувачі можуть додавати будь-кого до свого списку ворогів, але діють певні правила:

Якщо користувач $v$ вважає користувача $u$ своїм ворогом, це не означає, що $u$ автоматично вважає $v$ ворогом.
Користувач не може додати самого себе до списку ворогів.

Вінні-Пух у захваті від цієї соціальної мережі. Він проводить час, відстежуючи, хто з ким став ворогом, аби зрозуміти динаміку у своєму лісі. Він вважає, що ніхто не відвідуватиме свого ворога, а ворог ворога — друг. Відтак, Вінні-Пух вважає, що кожен повинен відвідувати своїх друзів. Він хоче дізнатися, скільки друзів має користувач $v$ . На його думку, користувач $u$ вважається другом користувача $v$ , якщо виконуються такі умови:

$u$ є ворогом ворога $v$ .
$u$ не є ворогом $v$ .

Крім того, жоден користувач не може бути сам собі другом.

Вхідні дані

Перший рядок містить два числа $n$ та $m$ ( $1 \leq n, m \leq 2000$ 1 \leq n, m \leq 2000), що позначають кількість користувачів у соціальній мережі та кількість запитів відповідно.

У наступних $m$ рядках записані запити двох типів:

$+$ $v$ $u$ — користувач $v$ почав вважати користувача $u$ ворогом.
$?$ $v$ — визначити кількість друзів користувача $v$ за критеріями Вінні-Пуха.

Гарантується, що дані коректні: користувач не вважає себе ворогом, і жоден користувач не буде доданий до списку ворогів більше одного разу.

Вихідні дані

Для кожного запиту виду $?$ $v$ виведіть у окремому рядку одне ціле число — відповідь на запит.

Приклади

Приклад 1