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 c++17.

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:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You are given an array of $$$n$$$ non-negative integers $$$a_1, a_2, \ldots, a_n$$$. You can make the following operation: choose an integer $$$x \geq 2$$$ and replace each number of the array by the remainder when dividing that number by $$$x$$$, that is, for all $$$1 \leq i \leq n$$$ set $$$a_i$$$ to $$$a_i \bmod x$$$.

Determine if it is possible to make all the elements of the array equal by applying the operation zero or more times.

## Input Format
The input consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases. Description of the test cases follows.

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

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq 10^9$$$) where $$$a_i$$$ is the $$$i$$$-th element of the array.

The sum of $$$n$$$ for all test cases is at most $$$2 \cdot 10^5$$$.

## Output Format
For each test case, print a line with YES if you can make all elements of the list equal by applying the operation. Otherwise, print NO.

You may print each letter in any case (for example, "YES", "Yes", "yes", "yEs" will all be recognized as a positive answer).

## Examples
```input
4
4
2 5 6 8
3
1 1 1
5
4 1 7 0 8
4
5 9 17 5
```
```output
YES
YES
NO
YES
```

## Note
In the first test case, one can apply the operation with $$$x = 3$$$ to obtain the array $$$[2, 2, 0, 2]$$$, and then apply the operation with $$$x = 2$$$ to obtain $$$[0, 0, 0, 0]$$$.

In the second test case, all numbers are already equal.

In the fourth test case, applying the operation with $$$x = 4$$$ results in the array $$$[1, 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 c++17.

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:
```cpp
<your code here>
```

Execution time limit: 3.0 seconds
Memory limit: 256.0 MB

# Problem
We say that a positive integer $$$n$$$ is $$$k$$$-good for some positive integer $$$k$$$ if $$$n$$$ can be expressed as a sum of $$$k$$$ positive integers which give $$$k$$$ distinct remainders when divided by $$$k$$$.

Given a positive integer $$$n$$$, find some $$$k \geq 2$$$ so that $$$n$$$ is $$$k$$$-good or tell that such a $$$k$$$ does not exist.

## Input Format
The input consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^5$$$) — the number of test cases.

Each test case consists of one line with an integer $$$n$$$ ($$$2 \leq n \leq 10^{18}$$$).

## Output Format
For each test case, print a line with a value of $$$k$$$ such that $$$n$$$ is $$$k$$$-good ($$$k \geq 2$$$), or $$$-1$$$ if $$$n$$$ is not $$$k$$$-good for any $$$k$$$. If there are multiple valid values of $$$k$$$, you can print any of them.

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

## Note
$$$6$$$ is a $$$3$$$-good number since it can be expressed as a sum of $$$3$$$ numbers which give different remainders when divided by $$$3$$$: $$$6 = 1 + 2 + 3$$$.

$$$15$$$ is also a $$$3$$$-good number since $$$15 = 1 + 5 + 9$$$ and $$$1, 5, 9$$$ give different remainders when divided by $$$3$$$.

$$$20$$$ is a $$$5$$$-good number since $$$20 = 2 + 3 + 4 + 5 + 6$$$ and $$$2,3,4,5,6$$$ give different remainders when divided by $$$5$$$.

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 c++17.

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:
```cpp
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
You are given an undirected unrooted tree, i.e. a connected undirected graph without cycles.

You must assign a nonzero integer weight to each vertex so that the following is satisfied: if any vertex of the tree is removed, then each of the remaining connected components has the same sum of weights in its vertices.

## Input Format
The input consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases. Description of the test cases follows.

The first line of each test case contains an integer $$$n$$$ ($$$3 \leq n \leq 10^5$$$) — the number of vertices of the tree.

The next $$$n-1$$$ lines of each case contain each two integers $$$u, v$$$ ($$$1 \leq u,v \leq n$$$) denoting that there is an edge between vertices $$$u$$$ and $$$v$$$. It is guaranteed that the given edges form a tree.

The sum of $$$n$$$ for all test cases is at most $$$10^5$$$.

## Output Format
For each test case, you must output one line with $$$n$$$ space separated integers $$$a_1, a_2, \ldots, a_n$$$, where $$$a_i$$$ is the weight assigned to vertex $$$i$$$. The weights must satisfy $$$-10^5 \leq a_i \leq 10^5$$$ and $$$a_i \neq 0$$$.

It can be shown that there always exists a solution satisfying these constraints. If there are multiple possible solutions, output any of them.

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

## Note
In the first case, when removing vertex $$$1$$$ all remaining connected components have sum $$$5$$$ and when removing vertex $$$3$$$ all remaining connected components have sum $$$2$$$. When removing other vertices, there is only one remaining connected component so all remaining connected components have the same sum.

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 c++17.

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:
```cpp
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
We say that a sequence of $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ is a palindrome if for all $$$1 \leq i \leq n$$$, $$$a_i = a_{n-i+1}$$$. You are given a sequence of $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ and you have to find, if it exists, a cycle permutation $$$\sigma$$$ so that the sequence $$$a_{\sigma(1)}, a_{\sigma(2)}, \ldots, a_{\sigma(n)}$$$ is a palindrome.

A permutation of $$$1, 2, \ldots, n$$$ is a bijective function from $$$\{1, 2, \ldots, n\}$$$ to $$$\{1, 2, \ldots, n\}$$$. We say that a permutation $$$\sigma$$$ is a cycle permutation if $$$1, \sigma(1), \sigma^2(1), \ldots, \sigma^{n-1}(1)$$$ are pairwise different numbers. Here $$$\sigma^m(1)$$$ denotes $$$\underbrace{\sigma(\sigma(\ldots \sigma}_{m \text{ times}}(1) \ldots))$$$.

## Input Format
The input consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 3 \cdot 10^4$$$) — the number of test cases. Description of the test cases follows.

The first line of each test case contains an integer $$$n$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$) — the size of the sequence.

The second line of each test case contains $$$n$$$ integers $$$a_1, \ldots, a_n$$$ ($$$1 \leq a_i \leq n$$$).

The sum of $$$n$$$ for all test cases is at most $$$2 \cdot 10^5$$$.

## Output Format
For each test case, output one line with YES if a cycle permutation exists, otherwise output one line with NO.

If the answer is YES, output one additional line with $$$n$$$ integers $$$\sigma(1), \sigma(2), \ldots, \sigma(n)$$$, the permutation. If there is more than one permutation, you may print any.

## Examples
```input
3
4
1 2 2 1
3
1 2 1
7
1 3 3 3 1 2 2
```
```output
YES
3 1 4 2 
NO
YES
5 3 7 2 6 4 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 c++17.

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:
```cpp
<your code here>
```

Execution time limit: 10.0 seconds
Memory limit: 512.0 MB

# Problem
You are given two sets of positive integers $$$A$$$ and $$$B$$$. You have to find two non-empty subsets $$$S_A \subseteq A$$$, $$$S_B \subseteq B$$$ so that the least common multiple (LCM) of the elements of $$$S_A$$$ is equal to the least common multiple (LCM) of the elements of $$$S_B$$$.

## Input Format
The input consists of multiple test cases. The first line of the input contains one integer $$$t$$$ ($$$1 \leq t \leq 200$$$), the number of test cases.

For each test case, there is one line containing two integers $$$n, m$$$ ($$$1 \leq n, m \leq 1000$$$), the sizes of the sets $$$A$$$ and $$$B$$$, respectively.

The next line contains $$$n$$$ distinct integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 4 \cdot 10^{36}$$$), the elements of $$$A$$$.

The next line contains $$$m$$$ distinct integers $$$b_1, b_2, \ldots, b_m$$$ ($$$1 \leq b_i \leq 4 \cdot 10^{36}$$$), the elements of $$$B$$$.

The sum of $$$n$$$ for all test cases and the sum of $$$m$$$ for all test cases is at most $$$1000$$$.

## Output Format
For each test case, if there do not exist two subsets with equal least common multiple, output one line with NO.

Otherwise, output one line with YES, followed by a line with two integers $$$|S_A|, |S_B|$$$ ($$$1 \leq |S_A| \leq n$$$, $$$1 \leq |S_B| \leq m$$$), the sizes of the subsets $$$S_A$$$ and $$$S_B$$$

The next line should contain $$$|S_A|$$$ integers $$$x_1, x_2, \ldots, x_{|S_A|}$$$, the elements of $$$S_A$$$, followed by a line with $$$|S_B|$$$ integers $$$y_1, y_2, \ldots, y_{|S_B|}$$$, the elements of $$$S_B$$$. If there are multiple possible pairs of subsets, you can print any.

## Examples
```input
4
3 4
5 6 7
2 8 9 10
4 4
5 6 7 8
2 3 4 9
1 3
1
1 2 3
5 6
3 4 9 7 8
2 15 11 14 20 12
```
```output
NO
YES
1 2
6
2 3
YES
1 1
1
1
YES
3 2
3 7 4
12 14
```

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 c++17.

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:
```cpp
<your code here>
```

Execution time limit: 5.0 seconds
Memory limit: 256.0 MB

# Problem
Given an undirected graph $$$G$$$, we say that a neighbour ordering is an ordered list of all the neighbours of a vertex for each of the vertices of $$$G$$$. Consider a given neighbour ordering of $$$G$$$ and three vertices $$$u$$$, $$$v$$$ and $$$w$$$, such that $$$v$$$ is a neighbor of $$$u$$$ and $$$w$$$. We write $$$u <_{v} w$$$ if $$$u$$$ comes after $$$w$$$ in $$$v$$$'s neighbor list.

A neighbour ordering is said to be good if, for each simple cycle $$$v_1, v_2, \ldots, v_c$$$ of the graph, one of the following is satisfied:

- $$$v_1 <_{v_2} v_3, v_2 <_{v_3} v_4, \ldots, v_{c-2} <_{v_{c-1}} v_c, v_{c-1} <_{v_c} v_1, v_c <_{v_1} v_2$$$.
- $$$v_1 >_{v_2} v_3, v_2 >_{v_3} v_4, \ldots, v_{c-2} >_{v_{c-1}} v_c, v_{c-1} >_{v_c} v_1, v_c >_{v_1} v_2$$$.

Given a graph $$$G$$$, determine whether there exists a good neighbour ordering for it and construct one if it does.

## Input Format
The input consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases. Description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$2 \leq n \leq 3 \cdot 10^5$$$, $$$1 \leq m \leq 3 \cdot 10^5$$$), the number of vertices and the number of edges of the graph.

The next $$$m$$$ lines each contain two integers $$$u, v$$$ ($$$0 \leq u, v < n$$$), denoting that there is an edge connecting vertices $$$u$$$ and $$$v$$$. It is guaranteed that the graph is connected and there are no loops or multiple edges between the same vertices.

The sum of $$$n$$$ and the sum of $$$m$$$ for all test cases are at most $$$3 \cdot 10^5$$$.

## Output Format
For each test case, output one line with YES if there is a good neighbour ordering, otherwise output one line with NO. You can print each letter in any case (upper or lower).

If the answer is YES, additionally output $$$n$$$ lines describing a good neighbour ordering. In the $$$i$$$-th line, output the neighbours of vertex $$$i$$$ in order.

If there are multiple good neigbour orderings, print any.

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

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 c++17.

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:
```cpp
<your code here>
```

Execution time limit: 3.0 seconds
Memory limit: 256.0 MB

# Problem
Consider every tree (connected undirected acyclic graph) with $$$n$$$ vertices ($$$n$$$ is odd, vertices numbered from $$$1$$$ to $$$n$$$), and for each $$$2 \le i \le n$$$ the $$$i$$$-th vertex is adjacent to exactly one vertex with a smaller index.

For each $$$i$$$ ($$$1 \le i \le n$$$) calculate the number of trees for which the $$$i$$$-th vertex will be the centroid. The answer can be huge, output it modulo $$$998\,244\,353$$$.

A vertex is called a centroid if its removal splits the tree into subtrees with at most $$$(n-1)/2$$$ vertices each.

## Input Format
The first line contains an odd integer $$$n$$$ ($$$3 \le n < 2 \cdot 10^5$$$, $$$n$$$ is odd) — the number of the vertices in the tree.

## Output Format
Print $$$n$$$ integers in a single line, the $$$i$$$-th integer is the answer for the $$$i$$$-th vertex (modulo $$$998\,244\,353$$$).

## Examples
```input
3
```
```output
1 1 0
```
-----
```input
5
```
```output
10 10 4 0 0
```
-----
```input
7
```
```output
276 276 132 36 0 0 0
```

## Note
Example $$$1$$$: there are two possible trees: with edges $$$(1-2)$$$, and $$$(1-3)$$$ — here the centroid is $$$1$$$; and with edges $$$(1-2)$$$, and $$$(2-3)$$$ — here the centroid is $$$2$$$. So the answer is $$$1, 1, 0$$$.

Example $$$2$$$: there are $$$24$$$ possible trees, for example with edges $$$(1-2)$$$, $$$(2-3)$$$, $$$(3-4)$$$, and $$$(4-5)$$$. Here the centroid is $$$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 c++17.

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:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Some country is populated by wizards. They want to organize a demonstration.

There are n people living in the city, x of them are the wizards who will surely go to the demonstration. Other city people (n - x people) do not support the wizards and aren't going to go to the demonstration. We know that the city administration will react only to the demonstration involving at least y percent of the city people. Having considered the matter, the wizards decided to create clone puppets which can substitute the city people on the demonstration.

So all in all, the demonstration will involve only the wizards and their puppets. The city administration cannot tell the difference between a puppet and a person, so, as they calculate the percentage, the administration will consider the city to be consisting of only n people and not containing any clone puppets.

Help the wizards and find the minimum number of clones to create to that the demonstration had no less than y percent of the city people.

## Input Format
The first line contains three space-separated integers, n, x, y (1 ≤ n, x, y ≤ 104, x ≤ n) — the number of citizens in the city, the number of wizards and the percentage the administration needs, correspondingly.

Please note that y can exceed 100 percent, that is, the administration wants to see on a demonstration more people that actually live in the city ( > n).

## Output Format
Print a single integer — the answer to the problem, the minimum number of clones to create, so that the demonstration involved no less than y percent of n (the real total city population).

## Examples
```input
10 1 14
```
```output
1
```
-----
```input
20 10 50
```
```output
0
```
-----
```input
1000 352 146
```
```output
1108
```

## Note
In the first sample it is necessary that at least 14% of 10 people came to the demonstration. As the number of people should be integer, then at least two people should come. There is only one wizard living in the city and he is going to come. That isn't enough, so he needs to create one clone.

In the second sample 10 people should come to the demonstration. The city has 10 wizards. They will all come to the demonstration, so nobody has to create any clones.

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 c++17.

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:
```cpp
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
You are given four distinct integers $$$a$$$, $$$b$$$, $$$c$$$, $$$d$$$.

Timur and three other people are running a marathon. The value $$$a$$$ is the distance that Timur has run and $$$b$$$, $$$c$$$, $$$d$$$ correspond to the distances the other three participants ran.

Output the number of participants in front of Timur.

## Input Format
The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases.

The description of each test case consists of four distinct integers $$$a$$$, $$$b$$$, $$$c$$$, $$$d$$$ ($$$0 \leq a, b, c, d \leq 10^4$$$).

## Output Format
For each test case, output a single integer — the number of participants in front of Timur.

## Examples
```input
4
2 3 4 1
10000 0 1 2
500 600 400 300
0 9999 10000 9998
```
```output
2
0
1
3
```

## Note
For the first test case, there are $$$2$$$ people in front of Timur, specifically the participants who ran distances of $$$3$$$ and $$$4$$$. The other participant is not in front of Timur because he ran a shorter distance than Timur.

For the second test case, no one is in front of Timur, since he ran a distance of $$$10000$$$ while all others ran a distance of $$$0$$$, $$$1$$$, and $$$2$$$ respectively.

For the third test case, only the second person is in front of Timur, who ran a total distance of $$$600$$$ while Timur ran a distance of $$$500$$$.

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 c++17.

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:
```cpp
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Sho has an array $$$a$$$ consisting of $$$n$$$ integers. An operation consists of choosing two distinct indices $$$i$$$ and $$$j$$$ and removing $$$a_i$$$ and $$$a_j$$$ from the array.

For example, for the array $$$[2, 3, 4, 2, 5]$$$, Sho can choose to remove indices $$$1$$$ and $$$3$$$. After this operation, the array becomes $$$[3, 2, 5]$$$. Note that after any operation, the length of the array is reduced by two.

After he made some operations, Sho has an array that has only distinct elements. In addition, he made operations such that the resulting array is the longest possible.

More formally, the array after Sho has made his operations respects these criteria:

- No pairs such that ($$$i < j$$$) and $$$a_i = a_j$$$ exist.
- The length of $$$a$$$ is maximized.

Output the length of the final array.

## Input Format
The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^3$$$) — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 50$$$) — the length of the array.

The second line of each test case contains $$$n$$$ integers $$$a_i$$$ ($$$1 \leq a_i \leq 10^4$$$) — the elements of the array.

## Output Format
For each test case, output a single integer — the length of the final array. Remember that in the final array, all elements are different, and its length is maximum.

## Examples
```input
4
6
2 2 2 3 3 3
5
9 1 9 9 1
4
15 16 16 15
4
10 100 1000 10000
```
```output
2
1
2
4
```

## Note
For the first test case Sho can perform operations as follows:

1. Choose indices $$$1$$$ and $$$5$$$ to remove. The array becomes $$$[2, 2, 2, 3, 3, 3] \rightarrow [2, 2, 3, 3]$$$.
2. Choose indices $$$1$$$ and $$$4$$$ to remove. The array becomes $$$[2, 2, 3, 3] \rightarrow [2, 3]$$$.

For the second test case Sho can perform operations as follows:

1. Choose indices $$$3$$$ and $$$4$$$ to remove. The array becomes $$$[9, 1, 9, 9, 1] \rightarrow [9, 1, 1]$$$.
2. Choose indices $$$1$$$ and $$$3$$$ to remove. The array becomes $$$[9, 1, 1] \rightarrow [1]$$$.

Now solve the problem and return the code.