favorite We need a little bit of your help to keep things running, click on this banner to learn more

Shortest paths - interesting graph problems

Mr. Nine and his love for mangoes

Mr.Nine was roaming casually in the Parralel Universe in his mid-semester breaks, suddenly he comes across a mango tree. He loves mangoes so he decide to pluck some mangoes from it but suddenly a fairy appears and tells him to solve a complex problem to get the mangoes. She tells him that there are n nodes in the trees and he is given two nodes u and v. Now she asks him how many pair of nodes are present in tree in which shortest path between them do not contains node v after node u (for example u -> a -> b -> v is also not allowed where a and b are two different nodes). If he is able to tell the correct number of pair of nodes then he will get all the mangoes,but he is unable to do and needs your help.


First line consists of integers n (1n300005), u and v. The following n - 1 lines consist of two space separated integers x and y denoting there is an edge between vertices x and y (1x, yn).


Find out the total number of pair of nodes.


There are 5 possible pairs that can be chosen:

(1, 2) : his route would be 12

(2, 3) : his route would be 23

(3, 2) : his route would be 32

(2, 1) : his route would be 21

(3, 1) : his route would be 321

He cannot choose (1, 3) as a pair because the shortest path between them will be 1 -> 2 -> 3 and this is not acceptable as it contains v after u and thus it is not acceptable.

Time limit 1 second
Memory limit 128 MiB
Input example #1
3 1 3
1 2
2 3
Output example #1