Куро живёт в стране Уберляндии, состоящей из \(n\) городов, пронумерованных от \(1\) до \(n\), и \(n - 1\) двусторонняя дорога, соединяющих эти города. Из каждого города можно добраться до любого другого. Каждая дорога соединяет два города \(a\) и \(b\). Куро любит пешие прогулки и поэтому планирует устроить пеший марафон — она выберет пару городов \((u, v)\) (\(u \neq v\)) и пройдёт от \(u\) до \(v\) по кратчайшему пути (заметим, что пары \((u, v)\) и \((v, u)\) считаются различными).
Как ни странно, в Уберляндии есть два особых города, один из которых — Цветниса (обозначается индексом \(x\)), а другой — Пчелополис (обозначается индексом \(y\)). Цветниса — город, в котором растёт много сильнопахнущих растений, а в Пчелополисе живёт много пчёл. Куро будет избегать такие пары городов \((u, v)\), если на пути от \(u\) до \(v\) он достигнет Пчелополиса после того, как он побывал в Цветнисе, поскольку пчёлы будут привлечены цветочным запахом и ужалят Куро.
Куро хочет узнать, сколько пар городов \((u, v)\) он может выбрать для своей пробежки. Так как задача нетривиальна, она обратилась за помощью к вам.
Выходные данные
Выведите одно целое число — количество пар городов \((u, v)\), которые Куро может использовать для пешего марафона.
Примечание
В первом примере Куро может выбрать следующие пары городов:
- \((1, 2)\): её маршрутом будет \(1 \rightarrow 2\),
- \((2, 3)\): её маршрутом будет \(2 \rightarrow 3\),
- \((3, 2)\): её маршрутом будет \(3 \rightarrow 2\),
- \((2, 1)\): её маршрутом будет \(2 \rightarrow 1\),
- \((3, 1)\): её маршрутом будет \(3 \rightarrow 2 \rightarrow 1\).
Куро не может выбрать пару \((1, 3)\), так как её маршрутом будет \(1 \rightarrow 2 \rightarrow 3\), в котором Куро сначала посетит город \(1\) (Цветнису), после чего посетит город \(3\) (Пчелополис), что запрещено (заметьте, что пара \((3, 1)\) является разрешённой, поскольку хотя Куро и посетила и Цветнису, и Пчелополис, она не посетила их в этом порядке).
Во втором примере, Куро может выбрать следующие пары городов:
- \((1, 2)\): её маршрутом будет \(1 \rightarrow 2\),
- \((2, 1)\): её маршрутом будет \(2 \rightarrow 1\),
- \((3, 2)\): её маршрутом будет \(3 \rightarrow 1 \rightarrow 2\),
- \((3, 1)\): её маршрутом будет \(3 \rightarrow 1\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 1 3
1 2
2 3
|
5
|
|
2
|
3 1 3
1 2
1 3
|
4
|