Tree Fun

David is a computer science student who loves his future profession. He is one of those who think that trees grow down, not up. David likes connected undirected acyclic graphs, also known as trees. He especially likes solving problems about trees. Recently David found a piece of paper with a tree with N vertices drawn on it. He also found M queries on the same piece of paper, where each query wa