Мистер Найн во время перерывов в середине семестра случайно бродил по вселенной Параллель и неожиданно наткнулся на манговое дерево. Он любит манго, поэтому решил его сорвать. Но внезапно появилась фея и дала ему решить сложную задачу. Дерево содержит n узлов. Заданы также два узла u и v. Фея спрашивает, сколько существует таких пар узлов в дереве, что кратчайший путь между ними не содержит узла v после узла u (например, u→a→b→v также не допускается, где a и b — два разных узла). Если мистер Найн сможет определить правильное количество пар узлов, то получит все манго. Однако он не в состоянии это сделать и нуждается в Вашей помощи.
Первая строка содержит числа n (1≤n≤300005), u и v. Каждая из следующих n−1 строк содержит два целых числа x и y означающих присутствие ребра между вершинами x и y (1≤x,y≤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, что не допустимо.