0246. Письма счастья

Имя входного файла:	letters.in
Имя выходного файла:	letters.out
Ограничение по времени:	2 s
Ограничение по памяти:	256 megabytes

В одной социальной сети стало популярным рассылать "письма счастья" – сообщения, с требованием, чтобы получатель распространил их копии другим адресатам. Администрация сети решила провести ранжирование своих пользователей, исходя из количества людей, с которыми они обменивались "письмами счастья".

Стажеру Васе было поручено написать программу, определяющую количество "несчастливых" пользователей (людей, состоящих в переписке с помощью таких писем не более чем с одним другим человеком). Причем сделать он это должен без получения прямого доступа к ящикам пользователей. При отправке сообщения, с помощью алгоритмов искусственного интеллекта проверяется, является ли оно "счастливым". Если условие выполняется, то на вход Васиной программе поступают идентификаторы отправителя и адресата.

Помогите Васе написать программу, решающую поставленную задачу.

Формат входного файла

В первой строке входного файла находятся два числа n и m (1 ≤ n ≤ 10⁵, 0 ≤ m ≤ 10⁵) – количество пользователей в социальной сети и количество отправленных сообщений. Следующие m строк содержат по два положительных числа a_i, b_i (1 ≤ a_i, b_i ≤ n) – идентификаторы отправителя и адресата.

Формат выходного файла

В выходной файл выведите количество искомых пользователей.

Пример:

letters.in	letters.out
6 5 1 2 2 1 2 4 3 5 4 3	3
3 3 1 2 2 3 3 1	0

Примечание: в первом примере ``несчастливые'' пользователи имеют идентификаторы 1, 5 и 6.

Источник: XXIII Городская олимпиада школьников г. Петрозаводска по информатике
Автор: Денис Власов

Обсудить       Отправить решение



Версия для печати