Problem D
Dying Tree
Time Limit : 2 seconds
 


Once upon the time in the forest, there were lots of trees who were all friends to one another. One of the trees T was very sick. She needed a tree doctor to save her life. As you may already know, trees can't move, but what you probably didn't know is that they can talk. Each tree t1 can talk to tree t2 if the minimum distance between any two branches from each is less than or equal to some value k. All trees decided to help their sick friend by trying to reach a doctor tree. They will continue to tell one another that tree T is sick until some tree S finds a tree doctor (who is at distance d or less from any branch of tree S). S will tell the doctor about her friend so he can go help her.

  • A tree is represented by a set of points representing her branches.

  • A doctor is represented by a single point.

 
  Input    
 

Input begins with a number t < 100 representing the number of test cases; t test cases follow. Each test case begins with 4 integers 0 < n < 100, 0 < m ≤ 10, 0 ≤ k, d ≤ 100 where n is the number of trees in the forest, m is the number of doctors in the forest, k & d are as described above. The next m lines represent the positions of doctors in x, y coordinates. The following lines describe the set of trees in the forest. Each set begins with an integer 0 < b < 10 representing the number of branches this tree has. Followed by b points representing the branches positions. The sick tree is always the first tree in the input. All points coordinates are integers with absolute values less than or equal to 1000.

 
     
  Output  
 

For each test case determine whether or not the trees can help their friend by finding a doctor for her. If yes, then print "Tree can be saved :)", if no then print "Tree can't be saved :(".

 
     
  Sample Input Sample Output    
 

2
3 2 2 3
3 8
7 4
4
0 0
1 1
3 2
2 0
3
6 -1
7 1
8 2
3
-1 -1
2 -3
5 -2
3 2 1 2
3 8
7 4
4
0 0
1 1
3 2
2 0
3
6 -1
7 1
8 2
3
-1 -1
2 -3
5 -2

Tree can be saved :)
Tree can't be saved :(

   
 

Problem Setter: Asmaa Magdi
Special Thanks: Muhammad Magdy
Alternate Solution: Sohel Hafiz

Illustration: The following diagram depicts Sample #1