github.com/captn3m0/codechef.git

---
category_name: medium
problem_code: KOL1503
problem_name: 'The Parenthesis Tree'
languages_supported:
    - C
    - CPP14
    - JAVA
max_timelimit: '2'
source_sizelimit: '50000'
problem_author: devuy11
problem_tester: null
date_added: 8-12-2015
tags:
    - acm15kol
    - ancestors
    - balanced
    - common
    - devuy11
    - lowest
    - parentheses
editorial_url: 'http://discuss.codechef.com/problems/KOL1503'
time:
    view_start_date: 1451123700
    submit_start_date: 1451123700
    visible_start_date: 1451123700
    end_date: 1735669800
    current: 1493557717
layout: problem
---
All submissions for this problem are available.Samosa Bhai and Jalebi Bai are taking cooking classes from CodeChef. CodeChef, as the name suggests, is also a coding enthusiast. So he decides to get his pupils interested in coding.

For this, he takes them both to a strange tree made up of **N** nodes. Each of these nodes is of one of the following two types — nodes containing open parenthesis **‘(’** and nodes containing closed parenthesis **‘)’**. CodeChef asks the students **Q** queries, where in each query they have to find out if the path between two given nodes is a balanced parentheses string or not. If they solve all the queries, they will get to eat the special Christmas cake made by CodeChef.

Samosa Bhai and Jalebi Bai are lazy kids, but they also want to eat the cake. So they ask you for help.

**Note:** A balanced parentheses string means that each opening parenthesis has a corresponding closing parenthesis and the pairs of parentheses are properly nested.

### Input

The first line contains **T**, the number of test cases to follow.

Each test case begins with **N** and **Q**, the number of nodes in the tree and the number of queries to follow.

**N-1** lines follow. Each line contains 2 space-separated integers, **x** and **y**, which denotes that there is an edge between them.

The next line contains **N** space-separated parentheses. The **ith** parenthesis denotes the value on the **ith** node.

The **Q** queries follow. Each query contains two space-separated integers **u** and **v**.

### Output

For each query, output "**Yes**" \[without quotes\] if the path from **u** to **v** is a balanced parentheses string and "**No**" \[without quotes\] if the path from **u** to **v** is not a balanced parentheses string.

### Constraints

- **1** ≤ **T** ≤ **1000**
- **1** ≤ **N** ≤ **105**
- **1** ≤ **Q** ≤ **3\*105**
- **1** ≤ **Sum of N over all cases** ≤ **105**
- **1** ≤ **Sum of Q over all cases** ≤ **3\*105**

### Example

<pre><b>Input:</b>
1
6 4
1 2
2 5
1 3
3 6
3 4
) ( ) ) ( (
5 3
3 5
2 4
6 2

<b>Output:</b>
Yes
No
No
No

</pre>### Explanation

**Example case 1.**

- **Query 1:** The path contains (()).
- **Query 2:** The path contains ))((.
- **Query 3:** The path contains ())).
- **Query 4:** The path contains ())(.



**NOTE:** Input files can be large. Please use fast input methods (E.g. scanf in C / C++, BufferedReader in Java)