Мистер Найн и его любовь к манго
Мистер Найн и его любовь к манго
Мистер Найн во время перерывов в середине семестра случайно бродил по вселенной Параллель и неожиданно наткнулся на манговое дерево. Он любит манго, поэтому решил его сорвать. Но внезапно появилась фея и дала ему решить сложную задачу. Дерево содержит 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, что не допустимо.
3 1 3 1 2 2 3
5