Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.


Limits: 1s, 512 MB

There is a house named Larcana. It is a very weird house .There are exactly N rooms in total and between any two adjacent rooms there is a door. You can reach any room from any other rooms by using one or more doors.

Now trump and putin are in two distinct rooms in this house. They are moving randomly in this house. In each second each of them chooses a door of his room randomly and uses it to go to an adjacent room.

If at any time . both of them are in the same room , a explosion occurs. So before putin and trump start to move , gabbar vai chooses a room randomly where none of them are in and destroys it to prevent the explosion .

You can assume the doors are built in such a way that they do not meet halfway changing rooms. For example, let room 1 and room 2 be adjacent. Then there is a door between them. If trump is in room 1 and putin is in room 2 then they can immediately switch room without meeting each other. After switching, trump will end up in room 2 and putin will end up in room 1. Since they did not meet in any particular room no explosion will occur.

Now find the probability that no explosion occurs.


In first line there will be a single integer T denotes the number of test cases. for each test cases, in the first line three integers N,R,P will be given which denotes the number of rooms in this house, the room number of Trump and the room number of Putin respectively. Then n-1 lines follow , pair of integers u and v denotes that room u and room v is adjacent and there is a door between them.

1 <= T <= 100

3 <= N <= 10000

1 <= P,R,u,v <=N , P ≠R


for each test cases, print two integers X and Y where the probability of no exposion is X/Y and X,Y are co-prime


3 1 3
1 2
2 3
4 1 3
1 2
2 3
3 4
1 1
1 2

In the first example: since putin and trump are in room 1 and room 3, Gabbar vai can destroy only room 2.

After the 1st second, putin can move to room 2 from room 1 and trump can move to room 2 from room 3. So they can meet in room 2 after the first second and it its the only such room.

So the probability here is : 11