Jonathan is making a connected tree of nodes, and bidirectional edges. He wants to give the tree to <REDACTED> for Valentine's Day. However, he wants to make sure the tree is *good looking*.

Jonathan defines a *simple* path in the tree as a path where every node is traversed at most once.

To determine whether the tree is *good looking*, he will give you queries that you must answer for him:

`v k u_1 u_2 ... u_k`

Is there a simple path that visits**in that order**, if at most bidirectional edges are added into the tree?

. is guaranteed to be distinct.

#### Input Specification

The first line will contain two integers, .

The next lines will each contain two integers , indicating that there is a bidirectional edge between and . It is guaranteed that the tree is connected.

The next lines will each contain a query as defined above.

#### Output Specification

For each query, output `1`

if the answer to the query is yes, and `0`

otherwise.

#### Subtasks

##### Subtask 1 [5%]

##### Subtask 2 [25%]

##### Subtask 3 [70%]

No further constraints.

#### Sample Input 1

```
5 3
1 2
2 3
2 4
1 5
0 3 5 2 3
0 3 3 4 5
0 3 1 3 2
```

#### Sample Output 1

```
1
0
0
```

#### Sample Input 2

```
7 5
1 2
2 3
2 4
4 5
5 6
5 7
0 3 3 4 7
0 4 2 5 7 6
1 4 2 5 7 6
2 5 3 4 2 1 7
1 6 6 5 7 4 1 3
```

#### Sample Output 2

```
1
0
1
1
0
```

## Comments