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

# Problem
Let's imagine that you're playing the following simple computer game. The screen displays n lined-up cubes. Each cube is painted one of m colors. You are allowed to delete not more than k cubes (that do not necessarily go one after another). After that, the remaining cubes join together (so that the gaps are closed) and the system counts the score. The number of points you score equals to the length of the maximum sequence of cubes of the same color that follow consecutively. Write a program that determines the maximum possible number of points you can score.

Remember, you may delete no more than k any cubes. It is allowed not to delete cubes at all.

## Input Format
The first line contains three integers n, m and k (1 ≤ n ≤ 2·105, 1 ≤ m ≤ 105, 0 ≤ k < n). The second line contains n integers from 1 to m — the numbers of cube colors. The numbers of colors are separated by single spaces.

## Output Format
Print the maximum possible number of points you can score.

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

## Note
In the first sample you should delete the fifth and the sixth cubes.

In the second sample you should delete the fourth and the seventh cubes.

In the third sample you shouldn't delete any cubes.

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
Students of group 199 have written their lectures dismally. Now an exam on Mathematical Analysis is approaching and something has to be done asap (that is, quickly). Let's number the students of the group from 1 to n. Each student i (1 ≤ i ≤ n) has a best friend p[i] (1 ≤ p[i] ≤ n). In fact, each student is a best friend of exactly one student. In other words, all p[i] are different. It is possible that the group also has some really "special individuals" for who i = p[i].

Each student wrote exactly one notebook of lecture notes. We know that the students agreed to act by the following algorithm:

- on the first day of revising each student studies his own Mathematical Analysis notes,
- in the morning of each following day each student gives the notebook to his best friend and takes a notebook from the student who calls him the best friend.

Thus, on the second day the student p[i] (1 ≤ i ≤ n) studies the i-th student's notes, on the third day the notes go to student p[p[i]] and so on. Due to some characteristics of the boys' friendship (see paragraph 1), each day each student has exactly one notebook to study.

You are given two sequences that describe the situation on the third and fourth days of revising:

- a1, a2, ..., an, where ai means the student who gets the i-th student's notebook on the third day of revising;
- b1, b2, ..., bn, where bi means the student who gets the i-th student's notebook on the fourth day of revising.

You do not know array p, that is you do not know who is the best friend to who. Write a program that finds p by the given sequences a and b.

## Input Format
The first line contains integer n (1 ≤ n ≤ 105) — the number of students in the group. The second line contains sequence of different integers a1, a2, ..., an (1 ≤ ai ≤ n). The third line contains the sequence of different integers b1, b2, ..., bn (1 ≤ bi ≤ n).

## Output Format
Print sequence n of different integers p[1], p[2], ..., p[n] (1 ≤ p[i] ≤ n). It is guaranteed that the solution exists and that it is unique.

## Examples
```input
4
2 1 4 3
3 4 2 1
```
```output
4 3 1 2
```
-----
```input
5
5 2 3 1 4
1 3 2 4 5
```
```output
4 3 2 5 1
```
-----
```input
2
1 2
2 1
```
```output
2 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
Ian and Mary are frogs living on lattice points of the Cartesian coordinate plane, with Ian living on $$$(0,0)$$$ and Mary living on $$$(a,b)$$$.

Ian would like to visit Mary by jumping around the Cartesian coordinate plane. Every second, he jumps from his current position $$$(x_p, y_p)$$$ to another lattice point $$$(x_q, y_q)$$$, such that no lattice point other than $$$(x_p, y_p)$$$ and $$$(x_q, y_q)$$$ lies on the segment between point $$$(x_p, y_p)$$$ and point $$$(x_q, y_q)$$$.

As Ian wants to meet Mary as soon as possible, he wants to jump towards point $$$(a,b)$$$ using at most $$$2$$$ jumps. Unfortunately, Ian is not good at maths. Can you help him?

A lattice point is defined as a point with both the $$$x$$$-coordinate and $$$y$$$-coordinate being integers.

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

The first and only line of each test case contains two integers $$$a$$$ and $$$b$$$ ($$$1\le a,b\le 10^9$$$) — the coordinates of the lattice point where Mary lives.

## Output Format
For each test case, print an integer $$$n$$$ ($$$1 \le n \le 2$$$) on the first line, denoting the number of jumps Ian uses in order to meet Mary. Note that you do not need to minimize the number of jumps.

On the $$$i$$$-th line of the next $$$n$$$ lines, print two integers $$$0 \le x_i,y_i \le 10^9$$$ separated by a space, denoting Ian's location $$$(x_i,y_i)$$$ after the $$$i$$$-th jump. $$$x_n = a$$$, $$$y_n = b$$$ must hold.

Ian's initial location and his locations after each of the $$$n$$$ jumps need not be distinct.

If there are multiple solutions, output any.

## Examples
```input
8
3 4
4 4
3 6
2 2
1 1
7 3
2022 2023
1000000000 1000000000
```
```output
1
3 4
2
3 2
4 4
2
5 3
3 6
2
1 0
2 2
1
1 1
1
7 3
1
2022 2023
2
69420420 469696969
1000000000 1000000000
```

## Note
In the first test case:

$$$(0,0) \to (3,4)$$$

In the second test case:

$$$(0,0) \to (3,2) \to (4,4)$$$

In the third test case:

$$$(0,0) \to (5,3) \to (3,6)$$$

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
Consider a $$$2 \times n$$$ grid, where $$$n$$$ is an even integer. You may place the integers $$$1, 2, \ldots, 2n$$$ on the grid, using each integer exactly once.

A path is a sequence of cells achieved by starting at $$$(1, 1)$$$, then repeatedly walking either downwards or to the right, and stopping when $$$(2, n)$$$ is reached. The path should not extend beyond the grid.

The cost of a path is the alternating sum of the numbers written on the cells in a path. That is, let the numbers written on the cells be $$$a_1, a_2, \ldots, a_k$$$ (in the order that it is visited), the cost of the path is $$$a_1 - a_2 + a_3 - a_4 + \ldots = \sum_{i=1}^k a_i \cdot (-1)^{i+1}$$$.

Construct a way to place the integers $$$1, 2, \ldots, 2n$$$ on the grid, such that the minimum cost over all paths from $$$(1, 1)$$$ to $$$(2, n)$$$ is maximized. If there are multiple such grids that result in the maximum value, output any of them.

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

The first and the only line of each test case contains a single integer $$$n$$$ ($$$2 \leq n \leq 10^5$$$, $$$n$$$ is even) — the number of the columns in the grid.

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

## Output Format
For each test case, output $$$2$$$ lines, each containing $$$n$$$ integers — the desired grid. If there are multiple solutions, output any of them.

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

## Note
In the first test case, there are only two paths from cell $$$(1, 1)$$$ to cell $$$(2, 2)$$$. Their costs are $$$3-1+4=6$$$ and $$$3-2+4=5$$$. Then the minimum cost is $$$5$$$, which is the maximum possible value.

In the second test case, there are four paths from cell $$$(1, 1)$$$ to cell $$$(2, 4)$$$. Their costs are $$$8-1+5-3+7=16$$$, $$$8-2+5-3+7=15$$$, $$$8-2+6-3+7=16$$$, and $$$8-2+6-4+7=15$$$. Then the minimum value is $$$15$$$, which is the maximum possible value.

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
Vlad decided to compose a melody on his guitar. Let's represent the melody as a sequence of notes corresponding to the characters 'a', 'b', 'c', 'd', 'e', 'f', and 'g'.

However, Vlad is not very experienced in playing the guitar and can only record exactly two notes at a time. Vlad wants to obtain the melody $$$s$$$, and to do this, he can merge the recorded melodies together. In this case, the last sound of the first melody must match the first sound of the second melody.

For example, if Vlad recorded the melodies "ab" and "ba", he can merge them together and obtain the melody "aba", and then merge the result with "ab" to get "abab".

Help Vlad determine the minimum number of melodies consisting of two notes that he needs to record in order to obtain the melody $$$s$$$.

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

Following that are the descriptions of the test cases.

The first line of each test case contains an integer $$$n$$$ ($$$2 \le n \le 50$$$) — the length of the melody $$$s$$$.

The second line of each test case contains a string $$$s$$$ of length $$$n$$$, consisting of characters 'a', 'b', 'c', 'd', 'e', 'f', 'g'.

## Output Format
Output $$$t$$$ integers, each representing the answer for the corresponding test case. As the answer output minimum number of melodies consisting of two notes that Vlad needs to record.

## Examples
```input
5
4
abab
7
abacaba
6
aaaaaa
7
abcdefg
5
babdd
```
```output
2
4
1
6
4
```

## Note
In the first sample, you need to record the melodies "ab" and "ba", as described in the problem statement.

In the second sample, you need to record the melodies "ab", "ba", "ac", and "ca".

In the third sample, the only necessary melody is "aa".

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
Vlad was given an array $$$a$$$ of $$$n$$$ positive integers. Now he wants to build a beautiful array $$$b$$$ of length $$$n$$$ from it.

Vlad considers an array beautiful if all the numbers in it are positive and have the same parity. That is, all numbers in the beautiful array are greater than zero and are either all even or all odd.

To build the array $$$b$$$, Vlad can assign each $$$b_i$$$ either the value $$$a_i$$$ or $$$a_i - a_j$$$, where any $$$j$$$ from $$$1$$$ to $$$n$$$ can be chosen.

To avoid trying to do the impossible, Vlad asks you to determine whether it is possible to build a beautiful array $$$b$$$ of length $$$n$$$ using his array $$$a$$$.

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

Then follow the descriptions of the test cases.

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

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

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

## Output Format
Output $$$t$$$ strings, each of which is the answer to the corresponding test case. As the answer, output "YES" if Vlad can build a beautiful array $$$b$$$, 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
7
5
2 6 8 4 3
5
1 4 7 6 9
4
2 6 4 10
7
5 29 13 9 10000001 11 3
5
2 1 2 4 2
5
2 4 5 4 3
4
2 5 5 4
```
```output
NO
YES
YES
YES
YES
NO
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 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
Ksyusha has a pet chinchilla, a tree on $$$n$$$ vertices and huge scissors. A tree is a connected graph without cycles. During a boring physics lesson Ksyusha thought about how to entertain her pet.

Chinchillas like to play with branches. A branch is a tree of $$$3$$$ vertices.

The branch looks like this.

A cut is the removal of some (not yet cut) edge in the tree. Ksyusha has plenty of free time, so she can afford to make enough cuts so that the tree splits into branches. In other words, after several (possibly zero) cuts, each vertex must belong to exactly one branch.

Help Ksyusha choose the edges to be cut or tell that it is impossible.

## Input Format
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — number of testcases.

The first line of each testcase contains a single integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — the number of vertices in the tree.

The next $$$n - 1$$$ rows of each testcase contain integers $$$v_i$$$ and $$$u_i$$$ ($$$1 \le v_i, u_i \le n$$$) — the numbers of vertices that the $$$i$$$-th edge connects.

It is guaranteed that this set of edges forms a tree. It is also guaranteed that the sum of $$$n$$$ over all testcases does not exceed $$$2 \cdot 10^5$$$.

## Output Format
Print the answer for each testcase.

If the desired way to cut the tree does not exist, print $$$-1$$$.

Otherwise, print an integer $$$k$$$ — the number of edges to be cut. In the next line, print $$$k$$$ different integers $$$e_i$$$ ($$$1 \le e_i < n$$$) — numbers of the edges to be cut. If $$$k = 0$$$, print an empty string instead.

If there are several solutions, you can print any.

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

1
2 
2
4 3
```

## Note
The first testcase in first test.

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 integer $$$n$$$, which you want to obtain. You have an unlimited supply of every integer from $$$1$$$ to $$$k$$$, except integer $$$x$$$ (there are no integer $$$x$$$ at all).

You are allowed to take an arbitrary amount of each of these integers (possibly, zero). Can you make the sum of taken integers equal to $$$n$$$?

If there are multiple answers, print any of them.

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

The only line of each testcase contains three integers $$$n, k$$$ and $$$x$$$ ($$$1 \le x \le k \le n \le 100$$$).

## Output Format
For each test case, in the first line, print "YES" or "NO" — whether you can take an arbitrary amount of each integer from $$$1$$$ to $$$k$$$, except integer $$$x$$$, so that their sum is equal to $$$n$$$.

If you can, the second line should contain a single integer $$$m$$$ — the total amount of taken integers. The third line should contain $$$m$$$ integers — each of them from $$$1$$$ to $$$k$$$, not equal to $$$x$$$, and their sum is $$$n$$$.

If there are multiple answers, print any of them.

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

## Note
Another possible answer for the first testcase is $$$[3, 3, 3, 1]$$$. Note that you don't have to minimize the amount of taken integers. There also exist other answers.

In the second testcase, you only have an unlimited supply of integer $$$2$$$. There is no way to get sum $$$5$$$ using only them.

In the fifth testcase, there are no integers available at all, so you can't get any positive 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 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
Bob and Carol hanged out with Alice the whole day, but now it's time to go home. Alice, Bob and Carol live on an infinite 2D grid in cells $$$A$$$, $$$B$$$, and $$$C$$$ respectively. Right now, all of them are in cell $$$A$$$.

If Bob (or Carol) is in some cell, he (she) can move to one of the neighboring cells. Two cells are called neighboring if they share a side. For example, the cell $$$(3, 5)$$$ has four neighboring cells: $$$(2, 5)$$$, $$$(4, 5)$$$, $$$(3, 6)$$$ and $$$(3, 4)$$$.

Bob wants to return to the cell $$$B$$$, Carol — to the cell $$$C$$$. Both of them want to go along the shortest path, i. e. along the path that consists of the minimum possible number of cells. But they would like to walk together as well.

What is the maximum possible number of cells that Bob and Carol can walk together if each of them walks home using one of the shortest paths?

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

The first line of each test case contains two integers $$$x_A$$$ and $$$y_A$$$ ($$$1 \le x_A, y_A \le 10^8$$$) — the position of cell $$$A$$$, where both Bob and Carol are right now.

The second line contains two integers $$$x_B$$$ and $$$y_B$$$ ($$$1 \le x_B, y_B \le 10^8$$$) — the position of cell $$$B$$$ (Bob's house).

The third line contains two integers $$$x_C$$$ and $$$y_C$$$ ($$$1 \le x_C, y_C \le 10^8$$$) — the position of cell $$$C$$$ (Carol's house).

Additional constraint on the input: the cells $$$A$$$, $$$B$$$, and $$$C$$$ are pairwise distinct in each test case.

## Output Format
For each test case, print the single integer — the maximum number of cells Bob and Carol can walk together if each of them goes home along one of the shortest paths.

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

## Note
In all pictures, red color denotes cells belonging only to Bob's path, light blue color — cells belonging only to Carol's path, and dark blue color — cells belonging to both paths.

One of the optimal routes for the first test case is shown below:

The optimal answer for the second test case is shown below:

One of the optimal answers for the third test case is shown below:

Now solve the problem and return the code.