У вас есть дерево из \(n\) вершин, а также \(m\) простых вершинных путей. Ваша задача — найти, сколько пар этих путей пересекаются по ровно одной вершине. Более формально, вам нужно найти число пар \((i, j)\) \((1 \leq i < j \leq m)\) таких, что \(path_i\) и \(path_j\) имеют ровно одну общую вершину.
Примечание
Дерево и пути в первом примере выглядят так. Пары \((1,4)\) и \((3,4)\) пересекаются по ровно одной вершине.
Во втором примере все пути состоят из единственной одинаковой вершины, так что все пары \((1, 2)\), \((1, 3)\) и \((2, 3)\) пересекаются по одной вершине.
Третий пример, такой же как первый, но с двумя дополнительными путями. Пары \((1,4)\), \((1,5)\), \((2,5)\), \((3,4)\), \((3,5)\), \((3,6)\) и \((5,6)\) пересекаются по ровно одной вершине.