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
Let's call an ordered pair of nodes $$$(u, v)$$$ in a directed graph unidirectional if $$$u \neq v$$$, there exists a path from $$$u$$$ to $$$v$$$, and there are no paths from $$$v$$$ to $$$u$$$.

A directed graph is called $$$p$$$-reachable if it contains exactly $$$p$$$ ordered pairs of nodes $$$(u, v)$$$ such that $$$u < v$$$ and $$$u$$$ and $$$v$$$ are reachable from each other. Find the minimum number of nodes required to create a $$$p$$$-reachable directed graph.

Also, among all such $$$p$$$-reachable directed graphs with the minimum number of nodes, let $$$G$$$ denote a graph which maximizes the number of unidirectional pairs of nodes. Find this number.

## Input Format
The first and only line contains a single integer $$$p$$$ ($$$0 \le p \le 2 \cdot 10^5$$$) — the number of ordered pairs of nodes.

## Output Format
Print a single line containing two integers — the minimum number of nodes required to create a $$$p$$$-reachable directed graph, and the maximum number of unidirectional pairs of nodes among all such $$$p$$$-reachable directed graphs with the minimum number of nodes.

## Examples
```input
3
```
```output
3 0
```
-----
```input
4
```
```output
5 6
```
-----
```input
0
```
```output
0 0
```

## Note
In the first test case, the minimum number of nodes required to create a $$$3$$$-reachable directed graph is $$$3$$$. Among all $$$3$$$-reachable directed graphs with $$$3$$$ nodes, the following graph $$$G$$$ is one of the graphs with the maximum number of unidirectional pairs of nodes, which is $$$0$$$.

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 an undirected, connected graph of $$$n$$$ nodes and $$$m$$$ edges. All nodes $$$u$$$ of the graph satisfy the following:

- Let $$$S_u$$$ be the set of vertices in the longest simple cycle starting and ending at $$$u$$$.
- Let $$$C_u$$$ be the union of the sets of vertices in any simple cycle starting and ending at $$$u$$$.
- $$$S_u = C_u$$$.

You need to answer $$$q$$$ queries.

For each query, you will be given node $$$a$$$ and node $$$b$$$. Out of all the edges that belong to any simple path from $$$a$$$ to $$$b$$$, count the number of edges such that if you remove that edge, $$$a$$$ and $$$b$$$ are reachable from each other.

## Input Format
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$1 \le m \le \min$$$($$$2 \cdot 10^5$$$, $$$(n \cdot (n-1))/2$$$)) — the total number of nodes and edges in the graph, respectively.

The next $$$m$$$ lines contain two integers $$$u$$$ and $$$v$$$ ($$$1 \le$$$ $$$u$$$, $$$v$$$ $$$\le n$$$, $$$u \neq v$$$) — describing an edge, implying that nodes $$$u$$$ and $$$v$$$ are connected to each other.

It is guaranteed that there is at most one edge between any pair of vertices in the graph and the given graph is connected.

The next line contains a single integer $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$) — the number of queries.

Then $$$q$$$ lines follow, each representing a query. Each query contains two integers $$$a$$$ and $$$b$$$ ($$$1 \le$$$ $$$a$$$, $$$b$$$ $$$\le n$$$).

## Output Format
For each query, output a single integer — answer to the query.

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

## Note
The graph in the first sample is :

The first query is $$$(1, 4)$$$. There are $$$5$$$ total edges that belong to any simple path from $$$1$$$ to $$$4$$$. Edges $$$(3, 4), (4, 5), (5, 3)$$$ will be counted in the answer to the query.

The fourth query is $$$(2, 8)$$$. There is only one simple path from $$$2$$$ to $$$8$$$, thus none of the edges will be counted in the answer to the query.

The fifth query is $$$(7, 10)$$$. There are $$$4$$$ total edges that belong to any simple path from $$$7$$$ to $$$10$$$, all of them will be counted in the answer to the query.

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
An array $$$a$$$ is good if for all pairs of adjacent elements, $$$a_i$$$ and $$$a_{i+1}$$$ ($$$1\le i \lt n$$$) are of different parity. Note that an array of size $$$1$$$ is trivially good.

You are given an array of size $$$n$$$.

In one operation you can select any pair of adjacent elements in which both elements are of the same parity, delete them, and insert their product in the same position.

Find the minimum number of operations to form a good array.

## Input Format
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 500$$$). The description of the test cases follows.

The first line of each test case contains an integer $$$n$$$ ($$$1 \le n \le 100$$$).

The second line of each test case contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le 10^{9}$$$).

## Output Format
For each test case print an integer, the minimum number of operations required to form a good array.

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

## Note
Consider the first test case. Select the $$$2$$$-nd and the $$$3$$$-rd integers and apply the operation on them. The array changes from $$$[1, \color{red}{7}, \color{red}{11}, 2, 13]$$$ to $$$[1, \color{red}{77}, 2, 13]$$$. Next, select the $$$1$$$-st and the $$$2$$$-nd integers, array changes from $$$[\color{red}{1}, \color{red}{77}, 2, 13]$$$ to $$$[\color{red}{77}, 2, 13]$$$. Thus we require $$$2$$$ operations. It can be proved that this is the minimum number of operations.

In the second test case, the given array is already good. So we require $$$0$$$ operations.

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 an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array), and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$ but there is $$$4$$$ in the array). There are $$$n! = n \cdot (n-1) \cdot (n - 2) \cdot \ldots \cdot 1$$$ different permutations of length $$$n$$$.

Given a permutation $$$p$$$ of $$$n$$$ numbers, we create an array $$$a$$$ consisting of $$$2n$$$ numbers, which is equal to $$$p$$$ concatenated with its reverse. We then define the beauty of $$$p$$$ as the number of inversions in $$$a$$$.

The number of inversions in the array $$$a$$$ is the number of pairs of indices $$$i$$$, $$$j$$$ such that $$$i < j$$$ and $$$a_i > a_j$$$.

For example, for permutation $$$p = [1, 2]$$$, $$$a$$$ would be $$$[1, 2, 2, 1]$$$. The inversions in $$$a$$$ are $$$(2, 4)$$$ and $$$(3, 4)$$$ (assuming 1-based indexing). Hence, the beauty of $$$p$$$ is $$$2$$$.

Your task is to find the sum of beauties of all $$$n!$$$ permutations of size $$$n$$$. Print the remainder we get when dividing this value by $$$1\,000\,000\,007$$$ ($$$10^9 + 7$$$).

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

Each test case has only one line — the integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$).

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

## Output Format
For each test case, print one integer — the sum of beauties of all permutations of size $$$n$$$ modulo $$$1\,000\,000\,007$$$ ($$$10^9 + 7$$$).

## Examples
```input
3
1
2
100
```
```output
0
4
389456655
```

## Note
For the first test case of the example, $$$p = [1]$$$ is the only permutation. $$$a = [1, 1]$$$ has $$$0$$$ inversions.

For the second test case of the example, the permutations are $$$[1, 2]$$$ and $$$[2, 1]$$$. Their respective $$$a$$$ arrays are $$$[1, 2, 2, 1]$$$ and $$$[2, 1, 1, 2]$$$, both of which have $$$2$$$ inversions.

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
A school has to decide on its team for an international quiz. There are $$$n$$$ students in the school. We can describe the students using an array $$$a$$$ where $$$a_i$$$ is the smartness of the $$$i$$$-th ($$$1 \le i \le n$$$) student.

There are $$$m$$$ topics $$$1, 2, 3, \ldots, m$$$ from which the quiz questions will be formed. The $$$i$$$-th student is considered proficient in a topic $$$T$$$ if $$$(a_i \bmod T) = 0$$$. Otherwise, he is a rookie in that topic.

We say that a team of students is collectively proficient in all the topics if for every topic there is a member of the team proficient in this topic.

Find a team that is collectively proficient in all the topics such that the maximum difference between the smartness of any two students in that team is minimized. Output this difference.

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

The first line of each test case contains $$$n$$$ and $$$m$$$ ($$$1 \le n,m \le 10^5$$$).

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^5$$$).

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

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

## Output Format
For each test case, print the answer on a new line. If there is no solution, output $$$-1$$$.

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

## Note
In the first test case, we have participants with smartnesses $$$3$$$ and $$$7$$$, and $$$m = 4$$$. Thus, there is no student with smartness divisible by $$$2$$$. Since $$$2 \leq m$$$, there is no way to choose a team.

In the second test case, we can select the participant with smartness $$$2$$$ to be the only one on the team. This way the team will be collectively proficient in both topics $$$1$$$ and $$$2$$$.

In the third test case, consider the team with participants of smartnesses $$$4, 5, 6, 7$$$. This way the team will be collectively proficient in all topics $$$1, 2, \ldots, 7$$$.

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

# Problem
You are given a tree of $$$n$$$ nodes, rooted at $$$1$$$. Every node has a value of either $$$0$$$ or $$$1$$$ at time $$$t=0$$$.

At any integer time $$$t>0$$$, the value of a node becomes the bitwise XOR of the values of its children at time $$$t - 1$$$; the values of leaves become $$$0$$$ since they don't have any children.

Let $$$S(t)$$$ denote the sum of values of all nodes at time $$$t$$$.

Let $$$F(A)$$$ denote the sum of $$$S(t)$$$ across all values of $$$t$$$ such that $$$0 \le t \le 10^{100}$$$, where $$$A$$$ is the initial assignment of $$$0$$$s and $$$1$$$s in the tree.

The task is to find the sum of $$$F(A)$$$ for all $$$2^n$$$ initial configurations of $$$0$$$s and $$$1$$$s in the tree. Print the sum modulo $$$10^9+7$$$.

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

The first line of each test case contains $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of nodes in the tree.

The next $$$n-1$$$ lines of each test case contain two integers each — $$$u$$$, $$$v$$$ indicating an edge between $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$).

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

## Output Format
Output the sum modulo $$$10^9+7$$$ for each test case.

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

## Note
Let us find $$$F(A)$$$ for the configuration $$$A = [0,1,0,0,1,1]$$$ ($$$A[i]$$$ denotes the value of node $$$i$$$). Initially (at $$$t = 0$$$) our tree is as shown in the picture below. In each node, two values are shown: the number and the value of this node. $$$S(0)$$$ for this configuration is $$$3$$$.

At $$$t = 1$$$ the configuration changes to $$$[1,0,0,0,0,0]$$$. The tree looks as shown below. $$$S(1) = 1$$$.

At $$$t = 2$$$ the configuration changes to $$$[0,0,0,0,0,0]$$$. The tree looks as shown below. $$$S(2) = 0$$$.

For all $$$t>2$$$, the graph remains unchanged, so $$$S(t)=0$$$ for all $$$t > 2$$$. So, for the initial configuration $$$A = [0,1,0,0,1,1]$$$, the value of $$$F(A) = 3 + 1 = 4$$$.

Doing this process for all possible $$$2^{6}$$$ configurations yields us an answer of $$$\textbf{288}$$$.

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: 8.0 seconds
Memory limit: 1024.0 MB

# Problem
You are given an array $$$a$$$ consisting of $$$n$$$ non-negative integers.

The numbness of a subarray $$$a_l, a_{l+1}, \ldots, a_r$$$ (for arbitrary $$$l \leq r$$$) is defined as $$$$$$\max(a_l, a_{l+1}, \ldots, a_r) \oplus (a_l \oplus a_{l+1} \oplus \ldots \oplus a_r),$$$$$$ where $$$\oplus$$$ denotes the bitwise XOR operation.

Find the maximum numbness over all subarrays.

## Input Format
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 1000$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$).

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq 10^9$$$).

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

## Output Format
For each test case, print one integer — the maximum numbness over all subarrays of the given array.

## Examples
```input
2
5
1 2 3 4 5
3
10 47 52
```
```output
7
47
```

## Note
For the first test case, for the subarray $$$[3, 4, 5]$$$, its maximum value is $$$5$$$. Hence, its numbness is $$$3 \oplus 4 \oplus 5 \oplus 5$$$ = $$$7$$$. This is the maximum possible numbness in this array.

In the second test case the subarray $$$[47, 52]$$$ provides the maximum numbness.

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
This is an easy version of the problem. In this version, all cards have the same color.

Alice has $$$n$$$ cards, each card is white, and the cards are stacked in a deck. Alice deals the cards to herself and to Bob, dealing at once several cards from the top of the deck in the following order: one card to herself, two cards to Bob, three cards to Bob, four cards to herself, five cards to herself, six cards to Bob, seven cards to Bob, eight cards to herself, and so on. In other words, on the $$$i$$$-th step, Alice deals $$$i$$$ top cards from the deck to one of the players; on the first step, she deals the cards to herself and then alternates the players every two steps. When there aren't enough cards at some step, Alice deals all the remaining cards to the current player, and the process stops.

First Alice's steps in a deck of many cards.

How many cards will Alice and Bob have at the end?

## Input Format
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 200$$$). The description of the test cases follows

The only line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^6$$$) — the number of cards.

## Output Format
For each test case print two integers — the number of cards in the end for each player — in this order: cards Alice has, cards Bob has.

## Examples
```input
5
10
6
17
8
1000000
```
```output
5 5
1 5
10 7
3 5
500202 499798
```

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
Monocarp is playing a computer game. He's going to kill $$$n$$$ monsters, the $$$i$$$-th of them has $$$h_i$$$ health.

Monocarp's character has two spells, either of which he can cast an arbitrary number of times (possibly, zero) and in an arbitrary order:

- choose exactly two alive monsters and decrease their health by $$$1$$$;
- choose a single monster and kill it.

When a monster's health becomes $$$0$$$, it dies.

What's the minimum number of spell casts Monocarp should perform in order to kill all monsters?

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

The first line of each testcase contains a single integer $$$n$$$ ($$$1 \le n \le 100$$$) — the number of monsters.

The second line contains $$$n$$$ integers $$$h_1, h_2, \dots, h_n$$$ ($$$1 \le h_i \le 100$$$) — the health of each monster.

The sum of $$$n$$$ over all testcases doesn't exceed $$$2 \cdot 10^4$$$.

## Output Format
For each testcase, print a single integer — the minimum number of spell casts Monocarp should perform in order to kill all monsters.

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

## Note
In the first testcase, the initial health list is $$$[1, 2, 1, 2]$$$. Three spells are casted:

- the first spell on monsters $$$1$$$ and $$$2$$$ — monster $$$1$$$ dies, monster $$$2$$$ has now health $$$1$$$, new health list is $$$[0, 1, 1, 2]$$$;
- the first spell on monsters $$$3$$$ and $$$4$$$ — monster $$$3$$$ dies, monster $$$4$$$ has now health $$$1$$$, new health list is $$$[0, 1, 0, 1]$$$;
- the first spell on monsters $$$2$$$ and $$$4$$$ — both monsters $$$2$$$ and $$$4$$$ die.

In the second testcase, the initial health list is $$$[2, 4, 2]$$$. Three spells are casted:

- the first spell on monsters $$$1$$$ and $$$3$$$ — both monsters have health $$$1$$$ now, new health list is $$$[1, 4, 1]$$$;
- the second spell on monster $$$2$$$ — monster $$$2$$$ dies, new health list is $$$[1, 0, 1]$$$;
- the first spell on monsters $$$1$$$ and $$$3$$$ — both monsters $$$1$$$ and $$$3$$$ die.

In the third testcase, the initial health list is $$$[1, 2, 3, 4, 5]$$$. Five spells are casted. The $$$i$$$-th of them kills the $$$i$$$-th monster with the second spell. Health list sequence: $$$[1, 2, 3, 4, 5]$$$ $$$\rightarrow$$$ $$$[0, 2, 3, 4, 5]$$$ $$$\rightarrow$$$ $$$[0, 0, 3, 4, 5]$$$ $$$\rightarrow$$$ $$$[0, 0, 0, 4, 5]$$$ $$$\rightarrow$$$ $$$[0, 0, 0, 0, 5]$$$ $$$\rightarrow$$$ $$$[0, 0, 0, 0, 0]$$$.

Now solve the problem and return the code.