Explosion

BUET CSE Fest 2019 Inter...
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 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.

Input

In first line there will be a single integer TT (1T1001 \le T \le 100) denotes the number of test cases. For each test cases, in the first line three integers NN (3N100003 \le N \le 10000), RR, PP (1P,RN,PR1 \le P, R \le N, P \ne R) 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 uu and vv (1u,vN1 \le u,v \le N) denotes that room uu and room vv is adjacent and there is a door between them.

Output

For each test cases, print two integers XX and YY where the probability of no explosion is XY\frac{X}{Y} and XX, YY are co-prime

Sample

InputOutput
2
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 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: 1/1.


Submit

Login to submit.

Statistics

83% Solution Ratio
ImaginaryNumberEarliest, Feb '19
masud_ali58Fastest, 0.0s
masud_ali58Lightest, 5.4 kB
Rajon68Shortest, 761B
Toph uses cookies. By continuing you agree to our Cookie Policy.