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
Naman has two binary strings $$$s$$$ and $$$t$$$ of length $$$n$$$ (a binary string is a string which only consists of the characters "0" and "1"). He wants to convert $$$s$$$ into $$$t$$$ using the following operation as few times as possible.

In one operation, he can choose any subsequence of $$$s$$$ and rotate it clockwise once.

For example, if $$$s = 1\textbf{1}101\textbf{00}$$$, he can choose a subsequence corresponding to indices ($$$1$$$-based) $$$\{2, 6, 7 \}$$$ and rotate them clockwise. The resulting string would then be $$$s = 1\textbf{0}101\textbf{10}$$$.

A string $$$a$$$ is said to be a subsequence of string $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by deleting some characters without changing the ordering of the remaining characters.

To perform a clockwise rotation on a sequence $$$c$$$ of size $$$k$$$ is to perform an operation which sets $$$c_1:=c_k, c_2:=c_1, c_3:=c_2, \ldots, c_k:=c_{k-1}$$$ simultaneously.

Determine the minimum number of operations Naman has to perform to convert $$$s$$$ into $$$t$$$ or say that it is impossible.

## Input Format
The first line contains a single integer $$$n$$$ $$$(1 \le n \le 10^6)$$$ — the length of the strings.

The second line contains the binary string $$$s$$$ of length $$$n$$$.

The third line contains the binary string $$$t$$$ of length $$$n$$$.

## Output Format
If it is impossible to convert $$$s$$$ to $$$t$$$ after any number of operations, print $$$-1$$$.

Otherwise, print the minimum number of operations required.

## Examples
```input
6
010000
000001
```
```output
1
```
-----
```input
10
1111100000
0000011111
```
```output
5
```
-----
```input
8
10101010
01010101
```
```output
1
```
-----
```input
10
1111100000
1111100001
```
```output
-1
```

## Note
In the first test, Naman can choose the subsequence corresponding to indices $$$\{2, 6\}$$$ and rotate it once to convert $$$s$$$ into $$$t$$$.

In the second test, he can rotate the subsequence corresponding to all indices $$$5$$$ times. It can be proved, that it is the minimum required number of operations.

In the last test, it is impossible to convert $$$s$$$ into $$$t$$$.

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 three positive (i.e. strictly greater than zero) integers $$$x$$$, $$$y$$$ and $$$z$$$.

Your task is to find positive integers $$$a$$$, $$$b$$$ and $$$c$$$ such that $$$x = \max(a, b)$$$, $$$y = \max(a, c)$$$ and $$$z = \max(b, c)$$$, or determine that it is impossible to find such $$$a$$$, $$$b$$$ and $$$c$$$.

You have to answer $$$t$$$ independent test cases. Print required $$$a$$$, $$$b$$$ and $$$c$$$ in any (arbitrary) order.

## Input Format
The first line of the input contains one integer $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$) — the number of test cases. Then $$$t$$$ test cases follow.

The only line of the test case contains three integers $$$x$$$, $$$y$$$, and $$$z$$$ ($$$1 \le x, y, z \le 10^9$$$).

## Output Format
For each test case, print the answer:

- "NO" in the only line of the output if a solution doesn't exist;
- or "YES" in the first line and any valid triple of positive integers $$$a$$$, $$$b$$$ and $$$c$$$ ($$$1 \le a, b, c \le 10^9$$$) in the second line. You can print $$$a$$$, $$$b$$$ and $$$c$$$ in any order.

## Examples
```input
5
3 2 3
100 100 100
50 49 49
10 30 20
1 1000000000 1000000000
```
```output
YES
3 2 1
YES
100 100 100
NO
NO
YES
1 1 1000000000
```

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
A permutation of length $$$n$$$ is a sequence of integers from $$$1$$$ to $$$n$$$ of length $$$n$$$ containing each number exactly once. For example, $$$[1]$$$, $$$[4, 3, 5, 1, 2]$$$, $$$[3, 2, 1]$$$ are permutations, and $$$[1, 1]$$$, $$$[0, 1]$$$, $$$[2, 2, 1, 4]$$$ are not.

There was a permutation $$$p[1 \dots n]$$$. It was merged with itself. In other words, let's take two instances of $$$p$$$ and insert elements of the second $$$p$$$ into the first maintaining relative order of elements. The result is a sequence of the length $$$2n$$$.

For example, if $$$p=[3, 1, 2]$$$ some possible results are: $$$[3, 1, 2, 3, 1, 2]$$$, $$$[3, 3, 1, 1, 2, 2]$$$, $$$[3, 1, 3, 1, 2, 2]$$$. The following sequences are not possible results of a merging: $$$[1, 3, 2, 1, 2, 3$$$], [$$$3, 1, 2, 3, 2, 1]$$$, $$$[3, 3, 1, 2, 2, 1]$$$.

For example, if $$$p=[2, 1]$$$ the possible results are: $$$[2, 2, 1, 1]$$$, $$$[2, 1, 2, 1]$$$. The following sequences are not possible results of a merging: $$$[1, 1, 2, 2$$$], [$$$2, 1, 1, 2]$$$, $$$[1, 2, 2, 1]$$$.

Your task is to restore the permutation $$$p$$$ by the given resulting sequence $$$a$$$. It is guaranteed that the answer exists and is unique.

You have to answer $$$t$$$ independent test cases.

## Input Format
The first line of the input contains one integer $$$t$$$ ($$$1 \le t \le 400$$$) — the number of test cases. Then $$$t$$$ test cases follow.

The first line of the test case contains one integer $$$n$$$ ($$$1 \le n \le 50$$$) — the length of permutation. The second line of the test case contains $$$2n$$$ integers $$$a_1, a_2, \dots, a_{2n}$$$ ($$$1 \le a_i \le n$$$), where $$$a_i$$$ is the $$$i$$$-th element of $$$a$$$. It is guaranteed that the array $$$a$$$ represents the result of merging of some permutation $$$p$$$ with the same permutation $$$p$$$.

## Output Format
For each test case, print the answer: $$$n$$$ integers $$$p_1, p_2, \dots, p_n$$$ ($$$1 \le p_i \le n$$$), representing the initial permutation. It is guaranteed that the answer exists and is unique.

## Examples
```input
5
2
1 1 2 2
4
1 3 1 4 3 4 2 2
5
1 2 1 2 3 4 3 5 4 5
3
1 2 3 1 2 3
4
2 3 2 4 1 3 4 1
```
```output
1 2 
1 3 4 2 
1 2 3 4 5 
1 2 3 
2 3 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 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
You are given a graph consisting of $$$n$$$ vertices and $$$m$$$ edges. It is not guaranteed that the given graph is connected. Some edges are already directed and you can't change their direction. Other edges are undirected and you have to choose some direction for all these edges.

You have to direct undirected edges in such a way that the resulting graph is directed and acyclic (i.e. the graph with all edges directed and having no directed cycles). Note that you have to direct all undirected edges.

You have to answer $$$t$$$ independent test cases.

## Input Format
The first line of the input contains one integer $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$) — the number of test cases. Then $$$t$$$ test cases follow.

The first line of the test case contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$1 \le m \le min(2 \cdot 10^5, \frac{n(n-1)}{2})$$$) — the number of vertices and the number of edges in the graph, respectively.

The next $$$m$$$ lines describe edges of the graph. The $$$i$$$-th edge is described with three integers $$$t_i$$$, $$$x_i$$$ and $$$y_i$$$ ($$$t_i \in [0; 1]$$$, $$$1 \le x_i, y_i \le n$$$) — the type of the edge ($$$t_i = 0$$$ if the edge is undirected and $$$t_i = 1$$$ if the edge is directed) and vertices this edge connects (the undirected edge connects vertices $$$x_i$$$ and $$$y_i$$$ and directed edge is going from the vertex $$$x_i$$$ to the vertex $$$y_i$$$). It is guaranteed that the graph do not contain self-loops (i.e. edges from the vertex to itself) and multiple edges (i.e. for each pair ($$$x_i, y_i$$$) there are no other pairs ($$$x_i, y_i$$$) or ($$$y_i, x_i$$$)).

It is guaranteed that both sum $$$n$$$ and sum $$$m$$$ do not exceed $$$2 \cdot 10^5$$$ ($$$\sum n \le 2 \cdot 10^5$$$; $$$\sum m \le 2 \cdot 10^5$$$).

## Output Format
For each test case print the answer — "NO" if it is impossible to direct undirected edges in such a way that the resulting graph is directed and acyclic, otherwise print "YES" on the first line and $$$m$$$ lines describing edges of the resulted directed acyclic graph (in any order). Note that you cannot change the direction of the already directed edges. If there are several answers, you can print any.

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

## Note
Explanation of the second test case of the example:

Explanation of the third test case of the example:

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 a tree (connected graph without cycles) consisting of $$$n$$$ vertices. The tree is unrooted — it is just a connected undirected graph without cycles.

In one move, you can choose exactly $$$k$$$ leaves (leaf is such a vertex that is connected to only one another vertex) connected to the same vertex and remove them with edges incident to them. I.e. you choose such leaves $$$u_1, u_2, \dots, u_k$$$ that there are edges $$$(u_1, v)$$$, $$$(u_2, v)$$$, $$$\dots$$$, $$$(u_k, v)$$$ and remove these leaves and these edges.

Your task is to find the maximum number of moves you can perform if you remove leaves optimally.

You have to answer $$$t$$$ independent test cases.

## Input Format
The first line of the input contains one integer $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$) — the number of test cases. Then $$$t$$$ test cases follow.

The first line of the test case contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 2 \cdot 10^5$$$; $$$1 \le k < n$$$) — the number of vertices in the tree and the number of leaves you remove in one move, respectively. The next $$$n-1$$$ lines describe edges. The $$$i$$$-th edge is represented as two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \le x_i, y_i \le n$$$), where $$$x_i$$$ and $$$y_i$$$ are vertices the $$$i$$$-th edge connects. It is guaranteed that the given set of edges forms a tree.

It is guaranteed that the sum of $$$n$$$ does not exceed $$$2 \cdot 10^5$$$ ($$$\sum n \le 2 \cdot 10^5$$$).

## Output Format
For each test case, print the answer — the maximum number of moves you can perform if you remove leaves optimally.

## Examples
```input
4
8 3
1 2
1 5
7 6
6 8
3 1
6 4
6 1
10 3
1 2
1 10
2 3
1 5
1 6
2 4
7 10
10 9
8 10
7 2
3 1
4 5
3 6
7 4
1 2
1 4
5 1
1 2
2 3
4 3
5 3
```
```output
2
3
3
4
```

## Note
The picture corresponding to the first test case of the example:

There you can remove vertices $$$2$$$, $$$5$$$ and $$$3$$$ during the first move and vertices $$$1$$$, $$$7$$$ and $$$4$$$ during the second move.

The picture corresponding to the second test case of the example:

There you can remove vertices $$$7$$$, $$$8$$$ and $$$9$$$ during the first move, then vertices $$$5$$$, $$$6$$$ and $$$10$$$ during the second move and vertices $$$1$$$, $$$3$$$ and $$$4$$$ during the third move.

The picture corresponding to the third test case of the example:

There you can remove vertices $$$5$$$ and $$$7$$$ during the first move, then vertices $$$2$$$ and $$$4$$$ during the second move and vertices $$$1$$$ and $$$6$$$ during the third move.

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 the array $$$a$$$ consisting of $$$n$$$ positive (greater than zero) integers.

In one move, you can choose two indices $$$i$$$ and $$$j$$$ ($$$i \ne j$$$) such that the absolute difference between $$$a_i$$$ and $$$a_j$$$ is no more than one ($$$|a_i - a_j| \le 1$$$) and remove the smallest of these two elements. If two elements are equal, you can remove any of them (but exactly one).

Your task is to find if it is possible to obtain the array consisting of only one element using several (possibly, zero) such moves or not.

You have to answer $$$t$$$ independent test cases.

## Input Format
The first line of the input contains one integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases. Then $$$t$$$ test cases follow.

The first line of the test case contains one integer $$$n$$$ ($$$1 \le n \le 50$$$) — the length of $$$a$$$. The second line of the test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 100$$$), where $$$a_i$$$ is the $$$i$$$-th element of $$$a$$$.

## Output Format
For each test case, print the answer: "YES" if it is possible to obtain the array consisting of only one element using several (possibly, zero) moves described in the problem statement, or "NO" otherwise.

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

## Note
In the first test case of the example, we can perform the following sequence of moves:

- choose $$$i=1$$$ and $$$j=3$$$ and remove $$$a_i$$$ (so $$$a$$$ becomes $$$[2; 2]$$$);
- choose $$$i=1$$$ and $$$j=2$$$ and remove $$$a_j$$$ (so $$$a$$$ becomes $$$[2]$$$).

In the second test case of the example, we can choose any possible $$$i$$$ and $$$j$$$ any move and it doesn't matter which element we remove.

In the third test case of the example, there is no way to get rid of $$$2$$$ and $$$4$$$.

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
There are $$$n$$$ people who want to participate in a boat competition. The weight of the $$$i$$$-th participant is $$$w_i$$$. Only teams consisting of two people can participate in this competition. As an organizer, you think that it's fair to allow only teams with the same total weight.

So, if there are $$$k$$$ teams $$$(a_1, b_1)$$$, $$$(a_2, b_2)$$$, $$$\dots$$$, $$$(a_k, b_k)$$$, where $$$a_i$$$ is the weight of the first participant of the $$$i$$$-th team and $$$b_i$$$ is the weight of the second participant of the $$$i$$$-th team, then the condition $$$a_1 + b_1 = a_2 + b_2 = \dots = a_k + b_k = s$$$, where $$$s$$$ is the total weight of each team, should be satisfied.

Your task is to choose such $$$s$$$ that the number of teams people can create is the maximum possible. Note that each participant can be in no more than one team.

You have to answer $$$t$$$ independent test cases.

## Input Format
The first line of the input contains one integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases. Then $$$t$$$ test cases follow.

The first line of the test case contains one integer $$$n$$$ ($$$1 \le n \le 50$$$) — the number of participants. The second line of the test case contains $$$n$$$ integers $$$w_1, w_2, \dots, w_n$$$ ($$$1 \le w_i \le n$$$), where $$$w_i$$$ is the weight of the $$$i$$$-th participant.

## Output Format
For each test case, print one integer $$$k$$$: the maximum number of teams people can compose with the total weight $$$s$$$, if you choose $$$s$$$ optimally.

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

## Note
In the first test case of the example, we can reach the optimal answer for $$$s=6$$$. Then the first boat is used by participants $$$1$$$ and $$$5$$$ and the second boat is used by participants $$$2$$$ and $$$4$$$ (indices are the same as weights).

In the second test case of the example, we can reach the optimal answer for $$$s=12$$$. Then first $$$6$$$ participants can form $$$3$$$ pairs.

In the third test case of the example, we can reach the optimal answer for $$$s=3$$$. The answer is $$$4$$$ because we have $$$4$$$ participants with weight $$$1$$$ and $$$4$$$ participants with weight $$$2$$$.

In the fourth test case of the example, we can reach the optimal answer for $$$s=4$$$ or $$$s=6$$$.

In the fifth test case of the example, we can reach the optimal answer for $$$s=3$$$. Note that participant with weight $$$3$$$ can't use the boat because there is no suitable pair for him in the list.

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 a binary string $$$s$$$ consisting of $$$n$$$ zeros and ones.

Your task is to divide the given string into the minimum number of subsequences in such a way that each character of the string belongs to exactly one subsequence and each subsequence looks like "010101 ..." or "101010 ..." (i.e. the subsequence should not contain two adjacent zeros or ones).

Recall that a subsequence is a sequence that can be derived from the given sequence by deleting zero or more elements without changing the order of the remaining elements. For example, subsequences of "1011101" are "0", "1", "11111", "0111", "101", "1001", but not "000", "101010" and "11100".

You have to answer $$$t$$$ independent test cases.

## Input Format
The first line of the input contains one integer $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$) — the number of test cases. Then $$$t$$$ test cases follow.

The first line of the test case contains one integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the length of $$$s$$$. The second line of the test case contains $$$n$$$ characters '0' and '1' — the string $$$s$$$.

It is guaranteed that the sum of $$$n$$$ does not exceed $$$2 \cdot 10^5$$$ ($$$\sum n \le 2 \cdot 10^5$$$).

## Output Format
For each test case, print the answer: in the first line print one integer $$$k$$$ ($$$1 \le k \le n$$$) — the minimum number of subsequences you can divide the string $$$s$$$ to. In the second line print $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le k$$$), where $$$a_i$$$ is the number of subsequence the $$$i$$$-th character of $$$s$$$ belongs to.

If there are several answers, you can print any.

## Examples
```input
4
4
0011
6
111111
5
10101
8
01010000
```
```output
2
1 2 2 1 
6
1 2 3 4 5 6 
1
1 1 1 1 1 
4
1 1 1 1 1 2 3 4
```

Now solve the problem and return the code.