Подразделы

Другие разделы

Дата и время

11/03/2025 20:40:10

Авторизация

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

Ограничения: время – 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$ выведите одно целое число – ответ на него в отдельной строке.

Пример ввода

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

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

Назад

Подразделы

Другие разделы

Дата и время

Авторизация

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

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