apaz/codeforces-genesys huggingface dataset:
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
This is an easy version of the problem. The only difference between an easy and a hard version is in the number of queries.

Polycarp grew a tree from $$$n$$$ vertices. We remind you that a tree of $$$n$$$ vertices is an undirected connected graph of $$$n$$$ vertices and $$$n-1$$$ edges that does not contain cycles.

He calls a set of vertices passable if there is such a path in the tree that passes through each vertex of this set without passing through any edge twice. The path can visit other vertices (not from this set).

In other words, a set of vertices is called passable if there is a simple path that passes through all the vertices of this set (and possibly some other).

For example, for a tree below sets $$$\{3, 2, 5\}$$$, $$$\{1, 5, 4\}$$$, $$$\{1, 4\}$$$ are passable, and $$$\{1, 3, 5\}$$$, $$$\{1, 2, 3, 4, 5\}$$$ are not.

Polycarp asks you to answer $$$q$$$ queries. Each query is a set of vertices. For each query, you need to determine whether the corresponding set of vertices is passable.

## Input Format
The first line of input contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — number of vertices.

Following $$$n - 1$$$ lines a description of the tree..

Each line contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \ne v$$$) — indices of vertices connected by an edge.

Following line contains single integer $$$q$$$ ($$$1 \le q \le 5$$$) — number of queries.

The following $$$2 \cdot q$$$ lines contain descriptions of sets.

The first line of the description contains an integer $$$k$$$ ($$$1 \le k \le n$$$) — the size of the set.

The second line of the description contains $$$k$$$ of distinct integers $$$p_1, p_2, \dots, p_k$$$ ($$$1 \le p_i \le n$$$) — indices of the vertices of the set.

It is guaranteed that the sum of $$$k$$$ values for all queries does not exceed $$$2 \cdot 10^5$$$.

## Output Format
Output $$$q$$$ lines, each of which contains the answer to the corresponding query. As an answer, output "YES" if the set is passable, and "NO" otherwise.

You can output the answer in any case (for example, the strings "yEs", "yes", "Yes" and "YES" will be recognized as a positive answer).

## Examples
```input
5
1 2
2 3
2 4
4 5
5
3
3 2 5
5
1 2 3 4 5
2
1 4
3
1 3 5
3
1 5 4
```
```output
YES
NO
YES
NO
YES
```
-----
```input
5
1 2
3 2
2 4
5 2
4
2
3 1
3
3 4 5
3
2 3 5
1
1
```
```output
YES
NO
YES
YES
```

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 1.5 seconds
Memory limit: 1024.0 MB

# Problem
You are given an integer array $$$a_1,\ldots, a_n$$$, where $$$1\le a_i \le n$$$ for all $$$i$$$.

There's a "replace" function $$$f$$$ which takes a pair of integers $$$(l, r)$$$, where $$$l \le r$$$, as input and outputs the pair $$$$$$f\big( (l, r) \big)=\left(\min\{a_l,a_{l+1},\ldots,a_r\},\, \max\{a_l,a_{l+1},\ldots,a_r\}\right).$$$$$$

Consider repeated calls of this function. That is, from a starting pair $$$(l, r)$$$ we get $$$f\big((l, r)\big)$$$, then $$$f\big(f\big((l, r)\big)\big)$$$, then $$$f\big(f\big(f\big((l, r)\big)\big)\big)$$$, and so on.

Now you need to answer $$$q$$$ queries. For the $$$i$$$-th query you have two integers $$$l_i$$$ and $$$r_i$$$ ($$$1\le l_i\le r_i\le n$$$). You must answer the minimum number of times you must apply the "replace" function to the pair $$$(l_i,r_i)$$$ to get $$$(1, n)$$$, or report that it is impossible.

## Input Format
The first line contains two positive integers $$$n$$$, $$$q$$$ ($$$1\le n,q\le 10^5$$$) — the length of the sequence $$$a$$$ and the number of the queries.

The second line contains $$$n$$$ positive integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1\le a_i\le n$$$) — the sequence $$$a$$$.

Each line of the following $$$q$$$ lines contains two integers $$$l_i$$$, $$$r_i$$$ ($$$1\le l_i\le r_i\le n$$$) — the queries.

## Output Format
For each query, output the required number of times, or $$$-1$$$ if it is impossible.

## Examples
```input
5 6
2 5 4 1 3
4 4
1 5
1 4
3 5
4 5
2 3
```
```output
-1
0
1
2
3
4
```
-----
```input
6 3
2 3 4 6 1 2
5 6
2 5
2 3
```
```output
5
1
3
```
-----
```input
5 3
3 2 2 4 1
2 5
1 3
1 5
```
```output
-1
-1
0
```

## Note
In the first example, $$$n=5$$$ and $$$a=[2,5,4,1,3]$$$.

For the first query: $$$(4,4)\to(1,1)\to(2,2)\to(5,5)\to(3,3)\to(4,4)\to\ldots$$$, so it's impossible to get $$$(1,5)$$$.

For the second query, you already have $$$(1,5)$$$.

For the third query: $$$(1,4)\to(1,5)$$$.

For the fourth query: $$$(3,5)\to(1,4)\to(1,5)$$$.

For the fifth query: $$$(4,5)\to(1,3)\to(2,5)\to(1,5)$$$.

For the sixth query: $$$(2,3)\to(4,5)\to(1,3)\to(2,5)\to(1,5)$$$.

Now solve the problem and return the code.