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
Pinkie Pie has bought a bag of patty-cakes with different fillings! But it appeared that not all patty-cakes differ from one another with filling. In other words, the bag contains some patty-cakes with the same filling.

Pinkie Pie eats the patty-cakes one-by-one. She likes having fun so she decided not to simply eat the patty-cakes but to try not to eat the patty-cakes with the same filling way too often. To achieve this she wants the minimum distance between the eaten with the same filling to be the largest possible. Herein Pinkie Pie called the distance between two patty-cakes the number of eaten patty-cakes strictly between them.

Pinkie Pie can eat the patty-cakes in any order. She is impatient about eating all the patty-cakes up so she asks you to help her to count the greatest minimum distance between the eaten patty-cakes with the same filling amongst all possible orders of eating!

Pinkie Pie is going to buy more bags of patty-cakes so she asks you to solve this problem for several bags!

## Input Format
The first line contains a single integer $$$T$$$ ($$$1 \le T \le 100$$$): the number of bags for which you need to solve the problem.

The first line of each bag description contains a single integer $$$n$$$ ($$$2 \le n \le 10^5$$$): the number of patty-cakes in it. The second line of the bag description contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$): the information of patty-cakes' fillings: same fillings are defined as same integers, different fillings are defined as different integers. It is guaranteed that each bag contains at least two patty-cakes with the same filling.

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

## Output Format
For each bag print in separate line one single integer: the largest minimum distance between the eaten patty-cakes with the same filling amongst all possible orders of eating for that bag.

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

## Note
For the first bag Pinkie Pie can eat the patty-cakes in the following order (by fillings): $$$1$$$, $$$6$$$, $$$4$$$, $$$7$$$, $$$1$$$, $$$6$$$, $$$4$$$ (in this way, the minimum distance is equal to $$$3$$$).

For the second bag Pinkie Pie can eat the patty-cakes in the following order (by fillings): $$$1$$$, $$$4$$$, $$$6$$$, $$$7$$$, $$$4$$$, $$$1$$$, $$$6$$$, $$$4$$$ (in this way, the minimum distance is equal to $$$2$$$).

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
Carousel Boutique is busy again! Rarity has decided to visit the pony ball and she surely needs a new dress, because going out in the same dress several times is a sign of bad manners. First of all, she needs a dress pattern, which she is going to cut out from the rectangular piece of the multicolored fabric.

The piece of the multicolored fabric consists of $$$n \times m$$$ separate square scraps. Since Rarity likes dresses in style, a dress pattern must only include scraps sharing the same color. A dress pattern must be the square, and since Rarity is fond of rhombuses, the sides of a pattern must form a $$$45^{\circ}$$$ angle with sides of a piece of fabric (that way it will be resembling the traditional picture of a rhombus).

Examples of proper dress patterns:  Examples of improper dress patterns:  The first one consists of multi-colored scraps, the second one goes beyond the bounds of the piece of fabric, the third one is not a square with sides forming a $$$45^{\circ}$$$ angle with sides of the piece of fabric.

Rarity wonders how many ways to cut out a dress pattern that satisfies all the conditions that do exist. Please help her and satisfy her curiosity so she can continue working on her new masterpiece!

## Input Format
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 2000$$$). Each of the next $$$n$$$ lines contains $$$m$$$ characters: lowercase English letters, the $$$j$$$-th of which corresponds to scrap in the current line and in the $$$j$$$-th column. Scraps having the same letter share the same color, scraps having different letters have different colors.

## Output Format
Print a single integer: the number of ways to cut out a dress pattern to satisfy all of Rarity's conditions.

## Examples
```input
3 3
aaa
aaa
aaa
```
```output
10
```
-----
```input
3 4
abab
baba
abab
```
```output
12
```
-----
```input
5 5
zbacg
baaac
aaaaa
eaaad
weadd
```
```output
31
```

## Note
In the first example, all the dress patterns of size $$$1$$$ and one of size $$$2$$$ are satisfactory.

In the second example, only the dress patterns of size $$$1$$$ are satisfactory.

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

# Problem
This is a harder version of the problem E with larger constraints.

Twilight Sparkle has received a new task from Princess Celestia. This time she asked to decipher the ancient scroll containing important knowledge of pony origin.

To hide the crucial information from evil eyes, pony elders cast a spell on the scroll. That spell adds exactly one letter in any place to each word it is cast on. To make the path to the knowledge more tangled elders chose some of words in the scroll and cast a spell on them.

Twilight Sparkle knows that the elders admired the order in all things so the scroll original scroll contained words in lexicographically non-decreasing order. She is asked to delete one letter from some of the words of the scroll (to undo the spell) to get some version of the original scroll.

Unfortunately, there may be more than one way to recover the ancient scroll. To not let the important knowledge slip by Twilight has to look through all variants of the original scroll and find the required one. To estimate the maximum time Twilight may spend on the work she needs to know the number of variants she has to look through. She asks you to find that number! Since that number can be very big, Twilight asks you to find it modulo $$$10^9+7$$$.

It may occur that princess Celestia has sent a wrong scroll so the answer may not exist.

A string $$$a$$$ is lexicographically smaller than a string $$$b$$$ if and only if one of the following holds:

- $$$a$$$ is a prefix of $$$b$$$, but $$$a \ne b$$$;
- in the first position where $$$a$$$ and $$$b$$$ differ, the string $$$a$$$ has a letter that appears earlier in the alphabet than the corresponding letter in $$$b$$$.

## Input Format
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$): the number of words in the scroll.

The $$$i$$$-th of the next $$$n$$$ lines contains a string consisting of lowercase English letters: the $$$i$$$-th word in the scroll. The length of each word is at least one. The sum of lengths of words does not exceed $$$10^6$$$.

## Output Format
Print one integer: the number of ways to get a version of the original from the scroll modulo $$$10^9+7$$$.

## Examples
```input
3
abcd
zaza
ataka
```
```output
4
```
-----
```input
4
dfs
bfs
sms
mms
```
```output
8
```
-----
```input
3
abc
bcd
a
```
```output
0
```
-----
```input
6
lapochka
kartyshka
bigbabytape
morgenshtern
ssshhhiiittt
queen
```
```output
2028
```

## Note
Notice that the elders could have written an empty word (but they surely cast a spell on it so it holds a length $$$1$$$ now).

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

# Problem
Shrimpy Duc is a fat and greedy boy who is always hungry. After a while of searching for food to satisfy his never-ending hunger, Shrimpy Duc finds M&M candies lying unguarded on a $$$L \times L$$$ grid. There are $$$n$$$ M&M candies on the grid, the $$$i$$$-th M&M is currently located at $$$(x_i + 0.5, y_i + 0.5),$$$ and has color $$$c_i$$$ out of a total of $$$k$$$ colors (the size of M&Ms are insignificant).

Shrimpy Duc wants to steal a rectangle of M&Ms, specifically, he wants to select a rectangle with integer coordinates within the grid and steal all candies within the rectangle. Shrimpy Duc doesn't need to steal every single candy, however, he would like to steal at least one candy for each color.

In other words, he wants to select a rectangle whose sides are parallel to the coordinate axes and whose left-bottom vertex $$$(X_1, Y_1)$$$ and right-top vertex $$$(X_2, Y_2)$$$ are points with integer coordinates satisfying $$$0 \le X_1 < X_2 \le L$$$ and $$$0 \le Y_1 < Y_2 \le L$$$, so that for every color $$$1 \le c \le k$$$ there is at least one M&M with color $$$c$$$ that lies within that rectangle.

How many such rectangles are there? This number may be large, so you only need to find it modulo $$$10^9 + 7$$$.

## Input Format
The first line contains three positive integers $$$n, k, L$$$ $$$(1 \leq k \leq n \leq 2 \cdot 10^3, 1 \leq L \leq 10^9 )$$$ — the number of M&Ms, the number of colors and the length of the grid respectively.

The following $$$n$$$ points describe the M&Ms. Each line contains three integers $$$x_i, y_i, c_i$$$ $$$(0 \leq x_i, y_i < L, 1 \le c_i \le k)$$$ — the coordinates and color of the $$$i$$$-th M&M respectively.

Different M&Ms have different coordinates ($$$x_i \ne x_j$$$ or $$$y_i \ne y_j$$$ for every $$$i \ne j$$$), and for every $$$1 \le c \le k$$$ there is at least one M&M with color $$$c$$$.

## Output Format
Output a single integer — the number of rectangles satisfying Shrimpy Duc's conditions, modulo $$$10^9 + 7$$$.

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

## Note
Grid for the first sample:

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

# Problem
You are given an integer $$$k$$$ and a tree $$$T$$$ with $$$n$$$ nodes ($$$n$$$ is even).

Let $$$dist(u, v)$$$ be the number of edges on the shortest path from node $$$u$$$ to node $$$v$$$ in $$$T$$$.

Let us define a undirected weighted complete graph $$$G = (V, E)$$$ as following:

- $$$V = \{x \mid 1 \le x \le n \}$$$ i.e. the set of integers from $$$1$$$ to $$$n$$$
- $$$E = \{(u, v, w) \mid 1 \le u, v \le n, u \neq v, w = dist(u, v) \}$$$ i.e. there is an edge between every pair of distinct nodes, the weight being the distance between their respective nodes in $$$T$$$

Your task is simple, find a perfect matching in $$$G$$$ with total edge weight $$$k$$$ $$$(1 \le k \le n^2)$$$.

## Input Format
The first line of input contains two integers $$$n$$$, $$$k$$$ ($$$2 \le n \le 100\,000$$$, $$$n$$$ is even, $$$1 \le k \le n^2$$$): number of nodes and the total edge weight of the perfect matching you need to find.

The $$$i$$$-th of the following $$$n - 1$$$ lines contains two integers $$$v_i$$$, $$$u_i$$$ ($$$1 \le v_i, u_i \le n$$$) denoting an edge between $$$v_i$$$ and $$$u_i$$$ in $$$T$$$. It is guaranteed that the given graph is a tree.

## Output Format
If there are no matchings that satisfy the above condition, output "NO" (without quotes) on a single line.

Otherwise, you should output "YES" (without quotes) on the first line of output.

You should then output $$$\frac{n}{2}$$$ lines, the $$$i$$$-th line containing $$$p_i, q_i$$$ ($$$1 \le p_i, q_i \le n$$$): the $$$i$$$-th pair of the matching.

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

## Note
A tree is a connected acyclic undirected graph.

A matching is set of pairwise non-adjacent edges, none of which are loops; that is, no two edges share a common vertex.

A perfect matching is a matching which matches all vertices of the graph; that is, every vertex of the graph is incident to exactly one edge of the matching.

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
Alexandra has an even-length array $$$a$$$, consisting of $$$0$$$s and $$$1$$$s. The elements of the array are enumerated from $$$1$$$ to $$$n$$$. She wants to remove at most $$$\frac{n}{2}$$$ elements (where $$$n$$$ — length of array) in the way that alternating sum of the array will be equal $$$0$$$ (i.e. $$$a_1 - a_2 + a_3 - a_4 + \dotsc = 0$$$). In other words, Alexandra wants sum of all elements at the odd positions and sum of all elements at the even positions to become equal. The elements that you remove don't have to be consecutive.

For example, if she has $$$a = [1, 0, 1, 0, 0, 0]$$$ and she removes $$$2$$$nd and $$$4$$$th elements, $$$a$$$ will become equal $$$[1, 1, 0, 0]$$$ and its alternating sum is $$$1 - 1 + 0 - 0 = 0$$$.

Help her!

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

The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 10^3$$$, $$$n$$$ is even)  — length of the array.

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

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

## Output Format
For each test case, firstly, print $$$k$$$ ($$$\frac{n}{2} \leq k \leq n$$$) — number of elements that will remain after removing in the order they appear in $$$a$$$. Then, print this $$$k$$$ numbers. Note that you should print the numbers themselves, not their indices.

We can show that an answer always exists. If there are several answers, you can output any of them.

## Examples
```input
4
2
1 0
2
0 0
4
0 1 1 1
4
1 1 0 0
```
```output
1
0
1
0
2
1 1
4
1 1 0 0
```

## Note
In the first and second cases, alternating sum of the array, obviously, equals $$$0$$$.

In the third case, alternating sum of the array equals $$$1 - 1 = 0$$$.

In the fourth case, alternating sum already equals $$$1 - 1 + 0 - 0 = 0$$$, so we don't have to remove anything.

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
There are $$$n$$$ beautiful skyscrapers in New York, the height of the $$$i$$$-th one is $$$h_i$$$. Today some villains have set on fire first $$$n - 1$$$ of them, and now the only safety building is $$$n$$$-th skyscraper.

Let's call a jump from $$$i$$$-th skyscraper to $$$j$$$-th ($$$i < j$$$) discrete, if all skyscrapers between are strictly lower or higher than both of them. Formally, jump is discrete, if $$$i < j$$$ and one of the following conditions satisfied:

- $$$i + 1 = j$$$
- $$$\max(h_{i + 1}, \ldots, h_{j - 1}) < \min(h_i, h_j)$$$
- $$$\max(h_i, h_j) < \min(h_{i + 1}, \ldots, h_{j - 1})$$$.

At the moment, Vasya is staying on the first skyscraper and wants to live a little longer, so his goal is to reach $$$n$$$-th skyscraper with minimal count of discrete jumps. Help him with calcualting this number.

## Input Format
The first line contains a single integer $$$n$$$ ($$$2 \le n \le 3 \cdot 10^5$$$) — total amount of skyscrapers.

The second line contains $$$n$$$ integers $$$h_1, h_2, \ldots, h_n$$$ ($$$1 \le h_i \le 10^9$$$) — heights of skyscrapers.

## Output Format
Print single number $$$k$$$ — minimal amount of discrete jumps. We can show that an answer always exists.

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

## Note
In the first testcase, Vasya can jump in the following way: $$$1 \rightarrow 2 \rightarrow 4 \rightarrow 5$$$.

In the second and third testcases, we can reach last skyscraper in one jump.

Sequence of jumps in the fourth testcase: $$$1 \rightarrow 3 \rightarrow 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
There are $$$n$$$ districts in the town, the $$$i$$$-th district belongs to the $$$a_i$$$-th bandit gang. Initially, no districts are connected to each other.

You are the mayor of the city and want to build $$$n-1$$$ two-way roads to connect all districts (two districts can be connected directly or through other connected districts).

If two districts belonging to the same gang are connected directly with a road, this gang will revolt.

You don't want this so your task is to build $$$n-1$$$ two-way roads in such a way that all districts are reachable from each other (possibly, using intermediate districts) and each pair of directly connected districts belong to different gangs, or determine that it is impossible to build $$$n-1$$$ roads to satisfy all the conditions.

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

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

The first line of the test case contains one integer $$$n$$$ ($$$2 \le n \le 5000$$$) — the number of districts. The second line of the test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$), where $$$a_i$$$ is the gang the $$$i$$$-th district belongs to.

It is guaranteed that the sum of $$$n$$$ does not exceed $$$5000$$$ ($$$\sum n \le 5000$$$).

## Output Format
For each test case, print:

- NO on the only line if it is impossible to connect all districts satisfying the conditions from the problem statement.
- YES on the first line and $$$n-1$$$ roads on the next $$$n-1$$$ lines. Each road should be presented as a pair of integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \le x_i, y_i \le n; x_i \ne y_i$$$), where $$$x_i$$$ and $$$y_i$$$ are two districts the $$$i$$$-th road connects.

For each road $$$i$$$, the condition $$$a[x_i] \ne a[y_i]$$$ should be satisfied. Also, all districts should be reachable from each other (possibly, using intermediate districts).

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

Now solve the problem and return the code.