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: 512.0 MB

# Problem
You are given $$$n-1$$$ integers $$$a_1, a_2, \dots, a_{n-1}$$$.

Your task is to construct an array $$$b_1, b_2, \dots, b_n$$$ such that:

- every integer from $$$0$$$ to $$$n-1$$$ appears in $$$b$$$ exactly once;
- for every $$$i$$$ from $$$1$$$ to $$$n-1$$$, $$$b_i \oplus b_{i+1} = a_i$$$ (where $$$\oplus$$$ denotes the bitwise XOR operator).

## Input Format
The first line contains one integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$).

The second line contains $$$n-1$$$ integers $$$a_1, a_2, \dots, a_{n-1}$$$ ($$$0 \le a_i \le 2n$$$).

Additional constraint on the input: it's always possible to construct at least one valid array $$$b$$$ from the given sequence $$$a$$$.

## Output Format
Print $$$n$$$ integers $$$b_1, b_2, \dots, b_n$$$. If there are multiple such arrays, you may print any of them.

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

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: 4.0 seconds
Memory limit: 512.0 MB

# Problem
Let's call an array $$$a$$$ of $$$n$$$ non-negative integers fancy if the following conditions hold:

- at least one from the numbers $$$x$$$, $$$x + 1$$$, ..., $$$x+k-1$$$ appears in the array;
- consecutive elements of the array differ by at most $$$k$$$ (i.e. $$$|a_i-a_{i-1}| \le k$$$ for each $$$i \in [2, n]$$$).

You are given $$$n$$$, $$$x$$$ and $$$k$$$. Your task is to calculate the number of fancy arrays of length $$$n$$$. Since the answer can be large, print it modulo $$$10^9+7$$$.

## Input Format
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 50$$$) — the number of test cases.

The only line of each test case contains three integers $$$n$$$, $$$x$$$ and $$$k$$$ ($$$1 \le n, k \le 10^9$$$; $$$0 \le x \le 40$$$).

## Output Format
For each test case, print a single integer — the number of fancy arrays of length $$$n$$$, taken modulo $$$10^9+7$$$.

## Examples
```input
4
3 0 1
1 4 25
4 7 2
1000000000 40 1000000000
```
```output
9
25
582
514035484
```

## Note
In the first test case of the example, the following arrays are fancy:

- $$$[0, 0, 0]$$$;
- $$$[0, 0, 1]$$$;
- $$$[0, 1, 0]$$$;
- $$$[0, 1, 1]$$$;
- $$$[0, 1, 2]$$$;
- $$$[1, 0, 0]$$$;
- $$$[1, 0, 1]$$$;
- $$$[1, 1, 0]$$$;
- $$$[2, 1, 0]$$$.

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: 3.0 seconds
Memory limit: 256.0 MB

# Problem
Berland starts to seize the initiative on the war with Flatland. To drive the enemy from their native land, the berlanders need to know exactly how many more flatland soldiers are left in the enemy's reserve. Fortunately, the scouts captured an enemy in the morning, who had a secret encrypted message with the information the berlanders needed so much.

The captured enemy had an array of positive integers. Berland intelligence have long been aware of the flatland code: to convey the message, which contained a number m, the enemies use an array of integers a. The number of its subarrays, in which there are at least k equal numbers, equals m. The number k has long been known in the Berland army so General Touristov has once again asked Corporal Vasya to perform a simple task: to decipher the flatlanders' message.

Help Vasya, given an array of integers a and number k, find the number of subarrays of the array of numbers a, which has at least k equal numbers.

Subarray a[i... j] (1 ≤ i ≤ j ≤ n) of array a = (a1, a2, ..., an) is an array, made from its consecutive elements, starting from the i-th one and ending with the j-th one: a[i... j] = (ai, ai + 1, ..., aj).

## Input Format
The first line contains two space-separated integers n, k (1 ≤ k ≤ n ≤ 4·105), showing how many numbers an array has and how many equal numbers the subarrays are required to have, correspondingly.

The second line contains n space-separated integers ai (1 ≤ ai ≤ 109) — elements of the array.

## Output Format
Print the single number — the number of such subarrays of array a, that they have at least k equal integers.

Please do not use the %lld specifier to read or write 64-bit integers in С++. In is preferred to use the cin, cout streams or the %I64d specifier.

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

## Note
In the first sample are three subarrays, containing at least two equal numbers: (1,2,1), (2,1,2) and (1,2,1,2).

In the second sample are two subarrays, containing three equal numbers: (1,2,1,1,3) and (1,2,1,1).

In the third sample any subarray contains at least one 1 number. Overall they are 6: (1), (1), (1), (1,1), (1,1) and (1,1,1).

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.0 seconds
Memory limit: 256.0 MB

# Problem
Filip has a row of cells, some of which are blocked, and some are empty. He wants all empty cells to have water in them. He has two actions at his disposal:

- $$$1$$$ — place water in an empty cell.
- $$$2$$$ — remove water from a cell and place it in any other empty cell.

If at some moment cell $$$i$$$ ($$$2 \le i \le n-1$$$) is empty and both cells $$$i-1$$$ and $$$i+1$$$ contains water, then it becomes filled with water.

Find the minimum number of times he needs to perform action $$$1$$$ in order to fill all empty cells with water.

Note that you don't need to minimize the use of action $$$2$$$. Note that blocked cells neither contain water nor can Filip place water in them.

## Input Format
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 100$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 100$$$) — the number of cells.

The next line contains a string $$$s$$$ of length $$$n$$$. The $$$i$$$-th character of $$$s$$$ is '.' if the cell $$$i$$$ is empty and '#' if cell $$$i$$$ is blocked.

## Output Format
For each test case, output a single number — the minimal amount of actions $$$1$$$ needed to fill all empty cells with water.

## Examples
```input
5
3
...
7
##....#
7
..#.#..
4
####
10
#...#..#.#
```
```output
2
2
5
0
2
```

## Note
Test Case 1

In the first test case, Filip can put water in cells $$$1$$$ and $$$3$$$. As cell $$$2$$$ is between $$$2$$$ cells with water, it gets filled with water too.

Test Case 2

In the second case, he can put water sources in cells $$$3$$$ and $$$5$$$. That results in cell $$$4$$$ getting filled with water. Then he will remove water from cell $$$5$$$ and place it into cell $$$6$$$. As cell $$$5$$$'s neighbors, cell $$$4$$$ and cell $$$6$$$, have water in them, cell $$$5$$$ also gets filled with water. You can see the illustration of this case below.

Operations in the second test case. White cells are empty, grey ones are blocked, and blue ones are water.

Test Case 3

In the third case, he can put water in all the empty cells. That requires $$$5$$$ actions of type $$$1$$$.

Test Case 4

In the fourth case, there are no empty cells. Therefore, he does not have to put any water in them.

Test Case 5

In the fifth test case, there exists a sequence of actions that requires only $$$2$$$ type $$$1$$$ actions.

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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Let $$$a$$$, $$$b$$$, and $$$c$$$ be integers. We define function $$$f(a, b, c)$$$ as follows:

Order the numbers $$$a$$$, $$$b$$$, $$$c$$$ in such a way that $$$a \le b \le c$$$. Then return $$$\gcd(a, b)$$$, where $$$\gcd(a, b)$$$ denotes the greatest common divisor (GCD) of integers $$$a$$$ and $$$b$$$.

So basically, we take the $$$\gcd$$$ of the $$$2$$$ smaller values and ignore the biggest one.

You are given an array $$$a$$$ of $$$n$$$ elements. Compute the sum of $$$f(a_i, a_j, a_k)$$$ for each $$$i$$$, $$$j$$$, $$$k$$$, such that $$$1 \le i < j < k \le n$$$.

More formally, compute $$$$$$\sum_{i = 1}^n \sum_{j = i+1}^n \sum_{k =j +1}^n f(a_i, a_j, a_k).$$$$$$

## Input Format
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$3 \le n \le 8 \cdot 10^4$$$) — length of the array $$$a$$$.

The second line of each test case contains $$$n$$$ integers, $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^5$$$) — elements of the array $$$a$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$8 \cdot 10^4$$$.

## Output Format
For each test case, output a single number — the sum from the problem statement.

## Examples
```input
2
5
2 3 6 12 17
8
6 12 8 10 15 12 18 16
```
```output
24
203
```

## Note
In the first test case, the values of $$$f$$$ are as follows:

- $$$i=1$$$, $$$j=2$$$, $$$k=3$$$, $$$f(a_i,a_j,a_k)=f(2,3,6)=\gcd(2,3)=1$$$;
- $$$i=1$$$, $$$j=2$$$, $$$k=4$$$, $$$f(a_i,a_j,a_k)=f(2,3,12)=\gcd(2,3)=1$$$;
- $$$i=1$$$, $$$j=2$$$, $$$k=5$$$, $$$f(a_i,a_j,a_k)=f(2,3,17)=\gcd(2,3)=1$$$;
- $$$i=1$$$, $$$j=3$$$, $$$k=4$$$, $$$f(a_i,a_j,a_k)=f(2,6,12)=\gcd(2,6)=2$$$;
- $$$i=1$$$, $$$j=3$$$, $$$k=5$$$, $$$f(a_i,a_j,a_k)=f(2,6,17)=\gcd(2,6)=2$$$;
- $$$i=1$$$, $$$j=4$$$, $$$k=5$$$, $$$f(a_i,a_j,a_k)=f(2,12,17)=\gcd(2,12)=2$$$;
- $$$i=2$$$, $$$j=3$$$, $$$k=4$$$, $$$f(a_i,a_j,a_k)=f(3,6,12)=\gcd(3,6)=3$$$;
- $$$i=2$$$, $$$j=3$$$, $$$k=5$$$, $$$f(a_i,a_j,a_k)=f(3,6,17)=\gcd(3,6)=3$$$;
- $$$i=2$$$, $$$j=4$$$, $$$k=5$$$, $$$f(a_i,a_j,a_k)=f(3,12,17)=\gcd(3,12)=3$$$;
- $$$i=3$$$, $$$j=4$$$, $$$k=5$$$, $$$f(a_i,a_j,a_k)=f(6,12,17)=\gcd(6,12)=6$$$.

In the second test case, there are $$$56$$$ ways to choose values of $$$i$$$, $$$j$$$, $$$k$$$. The sum over all $$$f(a_i,a_j,a_k)$$$ is $$$203$$$.

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.0 seconds
Memory limit: 256.0 MB

# Problem
You are given an array $$$a$$$ of $$$n$$$ positive integers and a score. If your score is greater than or equal to $$$a_i$$$, then you can increase your score by $$$a_i$$$ and remove $$$a_i$$$ from the array.

For each index $$$i$$$, output the maximum number of additional array elements that you can remove if you remove $$$a_i$$$ and then set your score to $$$a_i$$$. Note that the removal of $$$a_i$$$ should not be counted in the answer.

## Input Format
Each test contains multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 5000$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the length of the array.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the elements of the array.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

## Output Format
For each test case, output $$$n$$$ integers, the $$$i$$$-th of which denotes the maximum number of additional array elements that you can remove if you remove $$$a_i$$$ from the array and then set your score to $$$a_i$$$.

## Examples
```input
4
5
20 5 1 4 2
3
1434 7 1442
1
1
5
999999999 999999999 999999999 1000000000 1000000000
```
```output
4 3 0 3 1 
1 0 2 
0 
4 4 4 4 4
```

## Note
In the first test case, the answers are as follows:

If we start with $$$i=4$$$, our initial score is $$$a_4=4$$$ and $$$a=[20,5,1,2]$$$. We can remove $$$3$$$ additional elements in the following order:

1. Since $$$4 \ge 1$$$, we can remove $$$1$$$ and our score becomes $$$5$$$. After this, $$$a=[20,5,2]$$$.
2. Since $$$5 \ge 5$$$, we can remove $$$5$$$ and our score becomes $$$10$$$. After this, $$$a=[20,2]$$$.
3. Since $$$10 \ge 2$$$, we can remove $$$2$$$ and our score becomes $$$12$$$. After this, $$$a=[20]$$$.

If we start with $$$i=1$$$ we can remove all remaining elements in the array, so the answer is $$$4$$$.

If we start with $$$i=2$$$, we can remove $$$3$$$ additional elements in the following order: $$$1$$$, $$$4$$$, $$$2$$$.

If we start with $$$i=3$$$, we can remove no additional elements.

If we start with $$$i=5$$$, we can remove $$$1$$$ additional element: $$$1$$$.

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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You are given an array $$$a$$$ of $$$n$$$ positive integers. In one operation, you must pick some $$$(i, j)$$$ such that $$$1\leq i < j\leq |a|$$$ and append $$$|a_i - a_j|$$$ to the end of the $$$a$$$ (i.e. increase $$$n$$$ by $$$1$$$ and set $$$a_n$$$ to $$$|a_i - a_j|$$$). Your task is to minimize and print the minimum value of $$$a$$$ after performing $$$k$$$ operations.

## Input Format
Each test contains multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 1000$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$2\le n\le 2\cdot 10^3$$$, $$$1\le k\le 10^9$$$) — the length of the array and the number of operations you should perform.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1\le a_i\le 10^{18}$$$) — the elements of the array $$$a$$$.

It is guaranteed that the sum of $$$n^2$$$ over all test cases does not exceed $$$4\cdot 10^6$$$.

## Output Format
For each test case, print a single integer — the smallest possible value of the minimum of array $$$a$$$ after performing $$$k$$$ operations.

## Examples
```input
4
5 2
3 9 7 15 1
4 3
7 4 15 12
6 2
42 47 50 54 62 79
2 1
500000000000000000 1000000000000000000
```
```output
1
0
3
500000000000000000
```

## Note
In the first test case, after any $$$k=2$$$ operations, the minimum value of $$$a$$$ will be $$$1$$$.

In the second test case, an optimal strategy is to first pick $$$i=1, j=2$$$ and append $$$|a_1 - a_2| = 3$$$ to the end of $$$a$$$, creating $$$a=[7, 4, 15, 12, 3]$$$. Then, pick $$$i=3, j=4$$$ and append $$$|a_3 - a_4| = 3$$$ to the end of $$$a$$$, creating $$$a=[7, 4, 15, 12, 3, 3]$$$. In the final operation, pick $$$i=5, j=6$$$ and append $$$|a_5 - a_6| = 0$$$ to the end of $$$a$$$. Then the minimum value of $$$a$$$ will be $$$0$$$.

In the third test case, an optimal strategy is to first pick $$$i=2, j=3$$$ to append $$$|a_2 - a_3| = 3$$$ to the end of $$$a$$$. Any second operation will still not make the minimum value of $$$a$$$ be less than $$$3$$$.

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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
This is the easy version of the problem. The only differences between the two versions of this problem are the constraints on $$$n$$$ and the time limit. You can make hacks only if all versions of the problem are solved.

You are given two arrays $$$a$$$ and $$$b$$$ of length $$$n$$$.

You can perform the following operation some (possibly zero) times:

1. choose $$$l$$$ and $$$r$$$ such that $$$1 \leq l \leq r \leq n$$$.
2. let $$$x=\max(a_l,a_{l+1},\ldots,a_r)$$$.
3. for all $$$l \leq i \leq r$$$, set $$$a_i := x$$$.

Determine if you can make array $$$a$$$ equal to array $$$b$$$.

## Input Format
Each test contains multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 1000$$$) — the length of the arrays.

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

The third line contains $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \le b_i \le n$$$) — the elements of array $$$b$$$.

It is guaranteed that the sum of $$$n^2$$$ over all test cases does not exceed $$$10^6$$$.

## Output Format
For each test case, output "YES" (without quotes) if you can make $$$a$$$ into $$$b$$$ using any number of operations, and "NO" (without quotes) otherwise.

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

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

## Note
In the first test case, we can achieve array $$$b$$$ by applying a single operation: $$$(l,r)=(2,3)$$$.

In the second test case, it can be shown we cannot achieve array $$$b$$$ in any amount of operations.

In the third test case, we can achieve array $$$b$$$ by applying two operations: $$$(l,r)=(2,5)$$$. followed by $$$(l,r)=(1,3)$$$.

In the fourth and fifth test cases, it can be shown we cannot achieve array $$$b$$$ in any amount of operations.

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: 4.0 seconds
Memory limit: 512.0 MB

# Problem
Since Hayate didn't get any Christmas presents from Santa, he is instead left solving a tree query problem.

Hayate has a tree with $$$n$$$ nodes.

Hayate now wants you to answer $$$q$$$ queries. Each query consists of a node $$$x$$$ and $$$k$$$ other additional nodes $$$a_1,a_2,\ldots,a_k$$$. These $$$k+1$$$ nodes are guaranteed to be all distinct.

For each query, you must find the length of the longest simple path starting at node $$$x^\dagger$$$ after removing nodes $$$a_1,a_2,\ldots,a_k$$$ along with all edges connected to at least one of nodes $$$a_1,a_2,\ldots,a_k$$$.

$$$^\dagger$$$ A simple path of length $$$k$$$ starting at node $$$x$$$ is a sequence of distinct nodes $$$x=u_0,u_1,\ldots,u_k$$$ such that there exists a edge between nodes $$$u_{i-1}$$$ and $$$u_i$$$ for all $$$1 \leq i \leq k$$$.

## Input Format
The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n, q \le 2 \cdot 10^5$$$) — the number of nodes of the tree and the number of queries.

The following $$$n - 1$$$ lines contain two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \ne v$$$) — denoting an edge between nodes $$$u$$$ and $$$v$$$. It is guaranteed that the given edges form a tree.

The following $$$q$$$ lines describe the queries. Each line contains the integers $$$x$$$, $$$k$$$ and $$$a_1,a_2,\ldots,a_k$$$ ($$$1 \leq x \leq n$$$, $$$0 \leq k < n$$$, $$$1 \leq a_i \leq n$$$) — the starting node, the number of removed nodes and the removed nodes.

It is guaranteed that for each query, $$$x,a_1,a_2,\ldots,a_k$$$ are all distinct.

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

## Output Format
For each query, output a single integer denoting the answer for that query.

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

## Note
In the first example, the tree is as follows:

In the first query, no nodes are missing. The longest simple path starting from node $$$2$$$ is $$$2 \to 1 \to 3 \to 4$$$. Thus, the answer is $$$3$$$.

In the third query, nodes $$$1$$$ and $$$6$$$ are missing and the tree is shown below. The longest simple path starting from node $$$2$$$ is $$$2 \to 5$$$. Thus, the answer is $$$1$$$.

Now solve the problem and return the code.