eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Мистер Найн и его любовь к манго

Мистер Найн и его любовь к манго

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

Мистер Найн во время перерывов в середине семестра случайно бродил по вселенной Параллель и неожиданно наткнулся на манговое дерево. Он любит манго, поэтому решил его сорвать. Но внезапно появилась фея и дала ему решить сложную задачу. Дерево содержит n узлов. Заданы также два узла u и v. Фея спрашивает, сколько существует таких пар узлов в дереве, что кратчайший путь между ними не содержит узла v после узла u (например, u → a → b → v также не допускается, где a и b — два разных узла). Если мистер Найн сможет определить правильное количество пар узлов, то получит все манго. Однако он не в состоянии это сделать и нуждается в Вашей помощи.

Входные данные

Первая строка содержит числа n~(1 \le n \le 300005), u и v. Каждая из следующих n - 1 строк содержит два целых числа x и y означающих присутствие ребра между вершинами x и y~(1 \le x, y \le n).

Выходные данные

Выведите общее количество пар вершин.

Пример

Существует 5 возможных пар:

(1, 2) : его путь будет 1 → 2

(2, 3) : его путь будет 2 → 3

(3, 2) : его путь будет 3 → 2

(2, 1) : его путь будет 2 → 1

(3, 1) : его путь будет 3 → 2 → 1

Он не может выбрать (1, 3) в качестве пары, так как кратчайшим путем между ними будет 1 → 2 → 3 и он не приемлем, так как содержит v = 3 после u = 1, что не допустимо.

Входные данные #1
3 1 3
1 2
2 3
Выходные данные #1
5