Для анализа социальных сетей часто применяют понятие социального графа. В социальном графе пользователи являются вершинами, а каждое ребро показывает, что пользователи добавили друг друга в список друзей.
Исследователь собрал социальный граф для некоторых пользователей социальной сети Y. Этот граф хранится в виде одной таблицы friends со следующими полями:
- first_user_id — целое положительное число, идентификатор первого пользователя;
- second_user_id — целое положительное число, идентификатор второго пользователя.
При этом пара полей (first_user_id, second_user_id) является первичным ключом. Каждая такая пара для удобства хранится дважды. Например, если пользователи с ID 1 и 2 добавили друг друга в список друзей, таблица будет содержать две записи:
| first_user_id |
second_user_id |
| 1 |
2 |
| 2 |
1 |
Исследователь даёт несколько гарантий:
- дружба между двумя пользователями всегда хранится двумя строками;
- нет ситуаций, когда пользователь добавил в список друзей самого себя.
Два различных пользователя знают друг друга через одно рукопожатие, если существует третий пользователь, отличающийся от них и являющийся им другом, но при этом сами пользователи не являются друзьями. Иначе говоря, в социальном графе между этими пользователями нет ребра, но есть путь через одну вершину.
Определите, сколько различных пользователей знает пользователь с ID 10 через одно рукопожатие. Обратите внимание, что самого пользователя и его прямых друзей считать не нужно. В ответе введите одно целое неотрицательное число. Если пользователь с указанным ID не встречается в таблице, введите 0.
Примечание: файл с базой данных доступен в прикреплённых файлах.
Пример ввода ответа: 17