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

# Problem
You are given a directed acyclic graph with $$$n$$$ vertices and $$$m$$$ edges. For all edges $$$a \to b$$$ in the graph, $$$a < b$$$ holds.

You need to find the number of pairs of vertices $$$x$$$, $$$y$$$, such that $$$x > y$$$ and after adding the edge $$$x \to y$$$ to the graph, it has a Hamiltonian path.

## Input Format
The first line of input contains one integer $$$t$$$ ($$$1 \leq t \leq 5$$$): the number of test cases.

The next lines contains the descriptions of the test cases.

In the first line you are given two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n \leq 150\,000$$$, $$$0 \leq m \leq \min(150\,000, \frac{n(n-1)}{2})$$$): the number of vertices and edges in the graph.

Each of the next $$$m$$$ lines contains two integers $$$a$$$, $$$b$$$ ($$$1 \leq a < b \leq n$$$), specifying an edge $$$a \to b$$$ in the graph. No edge $$$a \to b$$$ appears more than once.

## Output Format
For each test case, print one integer: the number of pairs of vertices $$$x$$$, $$$y$$$, $$$x > y$$$, such that after adding the edge $$$x \to y$$$ to the graph, it has a Hamiltonian path.

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

## Note
In the first example, any edge $$$x \to y$$$ such that $$$x > y$$$ is valid, because there already is a path $$$1 \to 2 \to 3$$$.

In the second example only the edge $$$4 \to 1$$$ is valid. There is a path $$$3 \to 4 \to 1 \to 2$$$ if this edge is added.

In the third example you can add edges $$$2 \to 1$$$, $$$3 \to 1$$$, $$$4 \to 1$$$, $$$4 \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
You are given an array $$$a_1, a_2, \ldots, a_n$$$ and an integer $$$x$$$.

Find the number of non-empty subsets of indices of this array $$$1 \leq b_1 < b_2 < \ldots < b_k \leq n$$$, such that for all pairs $$$(i, j)$$$ where $$$1 \leq i < j \leq k$$$, the inequality $$$a_{b_i} \oplus a_{b_j} \leq x$$$ is held. Here, $$$\oplus$$$ denotes the bitwise XOR operation. As the answer may be very large, output it modulo $$$998\,244\,353$$$.

## Input Format
The first line of the input contains two integers $$$n$$$ and $$$x$$$ ($$$1 \leq n \leq 150\,000$$$, $$$0 \leq x < 2^{30}$$$). Here, $$$n$$$ is the size of the array.

The next line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i < 2^{30}$$$): the array itself.

## Output Format
Print one integer: the number of non-empty subsets such that the bitwise XOR of every pair of elements is at most $$$x$$$, modulo $$$998\,244\,353$$$.

## Examples
```input
4 2
0 1 2 3
```
```output
8
```
-----
```input
3 6
4 2 2
```
```output
7
```
-----
```input
4 0
1 1 2 2
```
```output
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 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 is a grid with $$$n$$$ rows and $$$m$$$ columns. Some cells are colored black, and the rest of the cells are colored white.

In one operation, you can select some black cell and do exactly one of the following:

- color all cells in its row black, or
- color all cells in its column black.

You are given two integers $$$r$$$ and $$$c$$$. Find the minimum number of operations required to make the cell in row $$$r$$$ and column $$$c$$$ black, or determine that it is impossible.

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

The first line of each test case contains four integers $$$n$$$, $$$m$$$, $$$r$$$, and $$$c$$$ ($$$1 \leq n, m \leq 50$$$; $$$1 \leq r \leq n$$$; $$$1 \leq c \leq m$$$) — the number of rows and the number of columns in the grid, and the row and column of the cell you need to turn black, respectively.

Then $$$n$$$ lines follow, each containing $$$m$$$ characters. Each of these characters is either 'B' or 'W' — a black and a white cell, respectively.

## Output Format
For each test case, if it is impossible to make the cell in row $$$r$$$ and column $$$c$$$ black, output $$$-1$$$.

Otherwise, output a single integer — the minimum number of operations required to make the cell in row $$$r$$$ and column $$$c$$$ black.

## Examples
```input
9
3 5 1 4
WBWWW
BBBWB
WWBBB
4 3 2 1
BWW
BBW
WBB
WWB
2 3 2 2
WWW
WWW
2 2 1 1
WW
WB
5 9 5 9
WWWWWWWWW
WBWBWBBBW
WBBBWWBWW
WBWBWBBBW
WWWWWWWWW
1 1 1 1
B
1 1 1 1
W
1 2 1 1
WB
2 1 1 1
W
B
```
```output
1
0
-1
2
2
0
-1
1
1
```

## Note
The first test case is pictured below.

We can take the black cell in row $$$1$$$ and column $$$2$$$, and make all cells in its row black. Therefore, the cell in row $$$1$$$ and column $$$4$$$ will become black.

In the second test case, the cell in row $$$2$$$ and column $$$1$$$ is already black.

In the third test case, it is impossible to make the cell in row $$$2$$$ and column $$$2$$$ black.

The fourth test case is pictured below.

We can take the black cell in row $$$2$$$ and column $$$2$$$ and make its column black.

Then, we can take the black cell in row $$$1$$$ and column $$$2$$$ and make its row black.

Therefore, the cell in row $$$1$$$ and column $$$1$$$ will become black.

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
You are given a tree of $$$n$$$ vertices numbered from $$$1$$$ to $$$n$$$, with edges numbered from $$$1$$$ to $$$n-1$$$. A tree is a connected undirected graph without cycles. You have to assign integer weights to each edge of the tree, such that the resultant graph is a prime tree.

A prime tree is a tree where the weight of every path consisting of one or two edges is prime. A path should not visit any vertex twice. The weight of a path is the sum of edge weights on that path.

Consider the graph below. It is a prime tree as the weight of every path of two or less edges is prime. For example, the following path of two edges: $$$2 \to 1 \to 3$$$ has a weight of $$$11 + 2 = 13$$$, which is prime. Similarly, the path of one edge: $$$4 \to 3$$$ has a weight of $$$5$$$, which is also prime.

Print any valid assignment of weights such that the resultant tree is a prime tree. If there is no such assignment, then print $$$-1$$$. It can be proven that if a valid assignment exists, one exists with weights between $$$1$$$ and $$$10^5$$$ as well.

## Input Format
The input consists of 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 one integer $$$n$$$ ($$$2 \leq n \leq 10^5$$$) — the number of vertices in the tree.

Then, $$$n-1$$$ lines follow. The $$$i$$$-th line contains two integers $$$u$$$ and $$$v$$$ ($$$1 \leq u, v \leq n$$$) denoting that edge number $$$i$$$ is between vertices $$$u$$$ and $$$v$$$. It is guaranteed that the edges form a tree.

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

## Output Format
For each test case, if a valid assignment exists, then print a single line containing $$$n-1$$$ integers $$$a_1, a_2, \dots, a_{n-1}$$$ ($$$1 \leq a_i \le 10^5$$$), where $$$a_i$$$ denotes the weight assigned to the edge numbered $$$i$$$. Otherwise, print $$$-1$$$.

If there are multiple solutions, you may print any.

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

## Note
For the first test case, there are only two paths having one edge each: $$$1 \to 2$$$ and $$$2 \to 1$$$, both having a weight of $$$17$$$, which is prime.

The second test case is described in the statement.

It can be proven that no such assignment exists for the third test case.

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
You have an array $$$a_1, a_2, \dots, a_n$$$ consisting of $$$n$$$ distinct integers. You are allowed to perform the following operation on it:

- Choose two elements from the array $$$a_i$$$ and $$$a_j$$$ ($$$i \ne j$$$) such that $$$\gcd(a_i, a_j)$$$ is not present in the array, and add $$$\gcd(a_i, a_j)$$$ to the end of the array. Here $$$\gcd(x, y)$$$ denotes greatest common divisor (GCD) of integers $$$x$$$ and $$$y$$$.

Note that the array changes after each operation, and the subsequent operations are performed on the new array.

What is the maximum number of times you can perform the operation on the array?

## Input Format
The first line consists of a single integer $$$n$$$ ($$$2 \le n \le 10^6$$$).

The second line consists of $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq 10^6$$$). All $$$a_i$$$ are distinct.

## Output Format
Output a single line containing one integer — the maximum number of times the operation can be performed on the given array.

## Examples
```input
5
4 20 1 25 30
```
```output
3
```
-----
```input
3
6 10 15
```
```output
4
```

## Note
In the first example, one of the ways to perform maximum number of operations on the array is:

- Pick $$$i = 1, j= 5$$$ and add $$$\gcd(a_1, a_5) = \gcd(4, 30) = 2$$$ to the array.
- Pick $$$i = 2, j= 4$$$ and add $$$\gcd(a_2, a_4) = \gcd(20, 25) = 5$$$ to the array.
- Pick $$$i = 2, j= 5$$$ and add $$$\gcd(a_2, a_5) = \gcd(20, 30) = 10$$$ to the array.

It can be proved that there is no way to perform more than $$$3$$$ operations on the original array.

In the second example one can add $$$3$$$, then $$$1$$$, then $$$5$$$, and $$$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
You are playing a very popular computer game. The next level consists of $$$n$$$ consecutive locations, numbered from $$$1$$$ to $$$n$$$, each of them containing either land or water. It is known that the first and last locations contain land, and for completing the level you have to move from the first location to the last. Also, if you become inside a location with water, you will die, so you can only move between locations with land.

You can jump between adjacent locations for free, as well as no more than once jump from any location with land $$$i$$$ to any location with land $$$i + x$$$, spending $$$x$$$ coins ($$$x \geq 0$$$).

Your task is to spend the minimum possible number of coins to move from the first location to the last one.

Note that this is always possible since both the first and last locations are the land locations.

## Input Format
There are several test cases in the input data. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 100$$$) — the number of test cases. This is followed by the test cases description.

The first line of each test case contains one integer $$$n$$$ ($$$2 \leq n \leq 100$$$) — the number of locations.

The second line of the test case contains a sequence of integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq 1$$$), where $$$a_i = 1$$$ means that the $$$i$$$-th location is the location with land, and $$$a_i = 0$$$ means that the $$$i$$$-th location is the location with water. It is guaranteed that $$$a_1 = 1$$$ and $$$a_n = 1$$$.

## Output Format
For each test case print a single integer — the answer to the problem.

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

## Note
In the first test case, it is enough to make one free jump from the first location to the second one, which is also the last one, so the answer is $$$0$$$.

In the second test case, the only way to move from the first location to the last one is to jump between them, which will cost $$$4$$$ coins.

In the third test case, you can jump from the first location to the third for $$$2$$$ coins, and then jump to the fourth location for free, so the answer is $$$2$$$. It can be shown that this is the optimal way.

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
Daniel is watching a football team playing a game during their training session. They want to improve their passing skills during that session.

The game involves $$$n$$$ players, making multiple passes towards each other. Unfortunately, since the balls were moving too fast, after the session Daniel is unable to know how many balls were involved during the game. The only thing he knows is the number of passes delivered by each player during all the session.

Find the minimum possible amount of balls that were involved in the game.

## Input Format
There are several test cases in the input data. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 5 \cdot 10^4$$$) — the number of test cases. This is followed by the test cases description.

The first line of each test case contains one integer $$$n$$$ ($$$2 \leq n \leq 10^5$$$) — the number of players.

The second line of the test case contains a sequence of integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq 10^9$$$), where $$$a_i$$$ is the number of passes delivered by the $$$i$$$-th player.

It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$10^5$$$.

## Output Format
For each test case print a single integer — the answer to the problem.

## Examples
```input
4
4
2 3 3 2
3
1 5 2
2
0 0
4
1000000000 1000000000 1000000000 1000000000
```
```output
1
2
0
1
```

## Note
In the first test case, with the only ball, the game can go like this:

$$$2 \rightarrow 1 \rightarrow 3 \rightarrow 4 \rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 2 \rightarrow 3 \rightarrow 2$$$.

In the second test case, there is no possible way to play the game with only one ball. One possible way to play with two balls:

$$$2 \rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow 2 \rightarrow 1$$$.

$$$2 \rightarrow 3 \rightarrow 2 \rightarrow 1$$$

In the third example, there were no passes, so $$$0$$$ balls are possible.

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
Recently, your friend discovered one special operation on an integer array $$$a$$$:

1. Choose two indices $$$i$$$ and $$$j$$$ ($$$i \neq j$$$);
2. Set $$$a_i = a_j = |a_i - a_j|$$$.

After playing with this operation for a while, he came to the next conclusion:

- For every array $$$a$$$ of $$$n$$$ integers, where $$$1 \le a_i \le 10^9$$$, you can find a pair of indices $$$(i, j)$$$ such that the total sum of $$$a$$$ will decrease after performing the operation.

This statement sounds fishy to you, so you want to find a counterexample for a given integer $$$n$$$. Can you find such counterexample and prove him wrong?

In other words, find an array $$$a$$$ consisting of $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) such that for all pairs of indices $$$(i, j)$$$ performing the operation won't decrease the total sum (it will increase or not change the sum).

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

The first and only line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 1000$$$) — the length of array $$$a$$$.

## Output Format
For each test case, if there is no counterexample array $$$a$$$ of size $$$n$$$, print NO.

Otherwise, print YES followed by the array $$$a$$$ itself ($$$1 \le a_i \le 10^9$$$). If there are multiple counterexamples, print any.

## Examples
```input
3
2
512
3
```
```output
YES
1 337
NO
YES
31 4 159
```

## Note
In the first test case, the only possible pairs of indices are $$$(1, 2)$$$ and $$$(2, 1)$$$.

If you perform the operation on indices $$$(1, 2)$$$ (or $$$(2, 1)$$$), you'll get $$$a_1 = a_2 = |1 - 337| = 336$$$, or array $$$[336, 336]$$$. In both cases, the total sum increases, so this array $$$a$$$ is a counterexample.

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
Let's denote the size of the maximum matching in a graph $$$G$$$ as $$$\mathit{MM}(G)$$$.

You are given a bipartite graph. The vertices of the first part are numbered from $$$1$$$ to $$$n$$$, the vertices of the second part are numbered from $$$n+1$$$ to $$$2n$$$. Each vertex's degree is $$$2$$$.

For a tuple of four integers $$$(l, r, L, R)$$$, where $$$1 \le l \le r \le n$$$ and $$$n+1 \le L \le R \le 2n$$$, let's define $$$G'(l, r, L, R)$$$ as the graph which consists of all vertices of the given graph that are included in the segment $$$[l, r]$$$ or in the segment $$$[L, R]$$$, and all edges of the given graph such that each of their endpoints belongs to one of these segments. In other words, to obtain $$$G'(l, r, L, R)$$$ from the original graph, you have to remove all vertices $$$i$$$ such that $$$i \notin [l, r]$$$ and $$$i \notin [L, R]$$$, and all edges incident to these vertices.

Calculate the sum of $$$\mathit{MM}(G(l, r, L, R))$$$ over all tuples of integers $$$(l, r, L, R)$$$ having $$$1 \le l \le r \le n$$$ and $$$n+1 \le L \le R \le 2n$$$.

## Input Format
The first line contains one integer $$$n$$$ ($$$2 \le n \le 1500$$$) — the number of vertices in each part.

Then $$$2n$$$ lines follow, each denoting an edge of the graph. The $$$i$$$-th line contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \le x_i \le n$$$; $$$n + 1 \le y_i \le 2n$$$) — the endpoints of the $$$i$$$-th edge.

There are no multiple edges in the given graph, and each vertex has exactly two incident edges.

## Output Format
Print one integer — the sum of $$$\mathit{MM}(G(l, r, L, R))$$$ over all tuples of integers $$$(l, r, L, R)$$$ having $$$1 \le l \le r \le n$$$ and $$$n+1 \le L \le R \le 2n$$$.

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

Now solve the problem and return the code.