It is Christmas in New York. This time Monica decided to decorate the Christmas tree using the colors Red and Black. Now Phoebe and Rachel also want to decorate the tree but Monica want to do all the work by herself so she gave them a problem to keep them busy. Since Phoebe and Rachel want to solve this problem as fast as possible so they need your help.
You are given a tree comprising of N nodes numbered 1-N. Each node can either be Red or Black (0 denotes Red and 1 denotes Black).The tree is rooted at node number 1. Root of the tree is at level number 1. You need to answer Q queries. In each query you will be given a level (X) and among all nodes in that level you need to find out the node which have maximum number of black nodes in its subtree an also the maximum number of black nodes. If there are multiple answers , print the minimum numbered node along with maximum black nodes in its subtree. The level of a node is defined by 1 + (the number of connections between the node and the root).
Initial input is T (test-cases) and for each test case-
First line contains an integer representing N the number of nodes. Next line contain n integers ,each representing the value(Ai) associated with each node from 1 to N (0 denotes Red and 1 denotes Black).
Next N - 1 lines contain two integers U and V each, which means that vertex U and V are connected to each other.
Next line contains an integer Q, the number of Queries. Next Q lines contain an integer X as described in the problem statement.
For each query print 2 integers(node number and the number of black nodes in its subtree) separated by space in a new line. If the level(X) does not exist ,then print -1 in a new line.