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
You are given a directed graph with $$$n$$$ vertices and $$$m$$$ directed edges without self-loops or multiple edges.

Let's denote the $$$k$$$-coloring of a digraph as following: you color each edge in one of $$$k$$$ colors. The $$$k$$$-coloring is good if and only if there no cycle formed by edges of same color.

Find a good $$$k$$$-coloring of given digraph with minimum possible $$$k$$$.

## Input Format
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n \le 5000$$$, $$$1 \le m \le 5000$$$) — the number of vertices and edges in the digraph, respectively.

Next $$$m$$$ lines contain description of edges — one per line. Each edge is a pair of integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \ne v$$$) — there is directed edge from $$$u$$$ to $$$v$$$ in the graph.

It is guaranteed that each ordered pair $$$(u, v)$$$ appears in the list of edges at most once.

## Output Format
In the first line print single integer $$$k$$$ — the number of used colors in a good $$$k$$$-coloring of given graph.

In the second line print $$$m$$$ integers $$$c_1, c_2, \dots, c_m$$$ ($$$1 \le c_i \le k$$$), where $$$c_i$$$ is a color of the $$$i$$$-th edge (in order as they are given in the input).

If there are multiple answers print any of them (you still have to minimize $$$k$$$).

## Examples
```input
4 5
1 2
1 3
3 4
2 4
1 4
```
```output
1
1 1 1 1 1
```
-----
```input
3 3
1 2
2 3
3 1
```
```output
2
1 1 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 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
There are $$$n$$$ football teams in the world.

The Main Football Organization (MFO) wants to host at most $$$m$$$ games. MFO wants the $$$i$$$-th game to be played between the teams $$$a_i$$$ and $$$b_i$$$ in one of the $$$k$$$ stadiums.

Let $$$s_{ij}$$$ be the numbers of games the $$$i$$$-th team played in the $$$j$$$-th stadium. MFO does not want a team to have much more games in one stadium than in the others. Therefore, for each team $$$i$$$, the absolute difference between the maximum and minimum among $$$s_{i1}, s_{i2}, \ldots, s_{ik}$$$ should not exceed $$$2$$$.

Each team has $$$w_i$$$ — the amount of money MFO will earn for each game of the $$$i$$$-th team. If the $$$i$$$-th team plays $$$l$$$ games, MFO will earn $$$w_i \cdot l$$$.

MFO needs to find what games in what stadiums they need to host in order to earn as much money as possible, not violating the rule they set.

However, this problem is too complicated for MFO. Therefore, they are asking you to help them.

## Input Format
The first line contains three integers $$$n$$$, $$$m$$$, $$$k$$$ ($$$3 \leq n \leq 100$$$, $$$0 \leq m \leq 1\,000$$$, $$$1 \leq k \leq 1\,000$$$) — the number of teams, the number of games, and the number of stadiums.

The second line contains $$$n$$$ integers $$$w_1, w_2, \ldots, w_n$$$ ($$$1 \leq w_i \leq 1\,000$$$) — the amount of money MFO will earn for each game of the $$$i$$$-th game.

Each of the following $$$m$$$ lines contains two integers $$$a_i$$$ and $$$b_i$$$ ($$$1 \leq a_i, b_i \leq n$$$, $$$a_i \neq b_i$$$) — the teams that can play the $$$i$$$-th game. It is guaranteed that each pair of teams can play at most one game.

## Output Format
For each game in the same order, print $$$t_i$$$ ($$$1 \leq t_i \leq k$$$) — the number of the stadium, in which $$$a_i$$$ and $$$b_i$$$ will play the game. If the $$$i$$$-th game should not be played, $$$t_i$$$ should be equal to $$$0$$$.

If there are multiple answers, print any.

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

## Note
One of possible solutions to the example is shown below:

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
The football season has just ended in Berland. According to the rules of Berland football, each match is played between two teams. The result of each match is either a draw, or a victory of one of the playing teams. If a team wins the match, it gets $$$w$$$ points, and the opposing team gets $$$0$$$ points. If the game results in a draw, both teams get $$$d$$$ points.

The manager of the Berland capital team wants to summarize the results of the season, but, unfortunately, all information about the results of each match is lost. The manager only knows that the team has played $$$n$$$ games and got $$$p$$$ points for them.

You have to determine three integers $$$x$$$, $$$y$$$ and $$$z$$$ — the number of wins, draws and loses of the team. If there are multiple answers, print any of them. If there is no suitable triple $$$(x, y, z)$$$, report about it.

## Input Format
The first line contains four integers $$$n$$$, $$$p$$$, $$$w$$$ and $$$d$$$ $$$(1 \le n \le 10^{12}, 0 \le p \le 10^{17}, 1 \le d < w \le 10^{5})$$$ — the number of games, the number of points the team got, the number of points awarded for winning a match, and the number of points awarded for a draw, respectively. Note that $$$w > d$$$, so the number of points awarded for winning is strictly greater than the number of points awarded for draw.

## Output Format
If there is no answer, print $$$-1$$$.

Otherwise print three non-negative integers $$$x$$$, $$$y$$$ and $$$z$$$ — the number of wins, draws and losses of the team. If there are multiple possible triples $$$(x, y, z)$$$, print any of them. The numbers should meet the following conditions:

- $$$x \cdot w + y \cdot d = p$$$,
- $$$x + y + z = n$$$.

## Examples
```input
30 60 3 1
```
```output
17 9 4
```
-----
```input
10 51 5 4
```
```output
-1
```
-----
```input
20 0 15 5
```
```output
0 0 20
```

## Note
One of the possible answers in the first example — $$$17$$$ wins, $$$9$$$ draws and $$$4$$$ losses. Then the team got $$$17 \cdot 3 + 9 \cdot 1 = 60$$$ points in $$$17 + 9 + 4 = 30$$$ games.

In the second example the maximum possible score is $$$10 \cdot 5 = 50$$$. Since $$$p = 51$$$, there is no answer.

In the third example the team got $$$0$$$ points, so all $$$20$$$ games were lost.

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 sequence $$$a_1, a_2, \dots, a_n$$$ consisting of $$$n$$$ integers.

You may perform the following operation on this sequence: choose any element and either increase or decrease it by one.

Calculate the minimum possible difference between the maximum element and the minimum element in the sequence, if you can perform the aforementioned operation no more than $$$k$$$ times.

## Input Format
The first line contains two integers $$$n$$$ and $$$k$$$ $$$(2 \le n \le 10^{5}, 1 \le k \le 10^{14})$$$ — the number of elements in the sequence and the maximum number of times you can perform the operation, respectively.

The second line contains a sequence of integers $$$a_1, a_2, \dots, a_n$$$ $$$(1 \le a_i \le 10^{9})$$$.

## Output Format
Print the minimum possible difference between the maximum element and the minimum element in the sequence, if you can perform the aforementioned operation no more than $$$k$$$ times.

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

## Note
In the first example you can increase the first element twice and decrease the third element twice, so the sequence becomes $$$[3, 3, 5, 5]$$$, and the difference between maximum and minimum is $$$2$$$. You still can perform one operation after that, but it's useless since you can't make the answer less than $$$2$$$.

In the second example all elements are already equal, so you may get $$$0$$$ as the answer even without applying any 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: 3.0 seconds
Memory limit: 256.0 MB

# Problem
Let's call a positive integer composite if it has at least one divisor other than $$$1$$$ and itself. For example:

- the following numbers are composite: $$$1024$$$, $$$4$$$, $$$6$$$, $$$9$$$;
- the following numbers are not composite: $$$13$$$, $$$1$$$, $$$2$$$, $$$3$$$, $$$37$$$.

You are given a positive integer $$$n$$$. Find two composite integers $$$a,b$$$ such that $$$a-b=n$$$.

It can be proven that solution always exists.

## Input Format
The input contains one integer $$$n$$$ ($$$1 \leq n \leq 10^7$$$): the given integer.

## Output Format
Print two composite integers $$$a,b$$$ ($$$2 \leq a, b \leq 10^9, a-b=n$$$).

It can be proven, that solution always exists.

If there are several possible solutions, you can print any.

## Examples
```input
1
```
```output
9 8
```
-----
```input
512
```
```output
4608 4096
```

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 new delivery of clothing has arrived today to the clothing store. This delivery consists of $$$a$$$ ties, $$$b$$$ scarves, $$$c$$$ vests and $$$d$$$ jackets.

The store does not sell single clothing items — instead, it sells suits of two types:

- a suit of the first type consists of one tie and one jacket;
- a suit of the second type consists of one scarf, one vest and one jacket.

Each suit of the first type costs $$$e$$$ coins, and each suit of the second type costs $$$f$$$ coins.

Calculate the maximum possible cost of a set of suits that can be composed from the delivered clothing items. Note that one item cannot be used in more than one suit (though some items may be left unused).

## Input Format
The first line contains one integer $$$a$$$ $$$(1 \le a \le 100\,000)$$$ — the number of ties.

The second line contains one integer $$$b$$$ $$$(1 \le b \le 100\,000)$$$ — the number of scarves.

The third line contains one integer $$$c$$$ $$$(1 \le c \le 100\,000)$$$ — the number of vests.

The fourth line contains one integer $$$d$$$ $$$(1 \le d \le 100\,000)$$$ — the number of jackets.

The fifth line contains one integer $$$e$$$ $$$(1 \le e \le 1\,000)$$$ — the cost of one suit of the first type.

The sixth line contains one integer $$$f$$$ $$$(1 \le f \le 1\,000)$$$ — the cost of one suit of the second type.

## Output Format
Print one integer — the maximum total cost of some set of suits that can be composed from the delivered items.

## Examples
```input
4
5
6
3
1
2
```
```output
6
```
-----
```input
12
11
13
20
4
6
```
```output
102
```
-----
```input
17
14
5
21
15
17
```
```output
325
```

## Note
It is possible to compose three suits of the second type in the first example, and their total cost will be $$$6$$$. Since all jackets will be used, it's impossible to add anything to this set.

The best course of action in the second example is to compose nine suits of the first type and eleven suits of the second type. The total cost is $$$9 \cdot 4 + 11 \cdot 6 = 102$$$.

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$$$ blocks arranged in a row and numbered from left to right, starting from one. Each block is either black or white.

You may perform the following operation zero or more times: choose two adjacent blocks and invert their colors (white block becomes black, and vice versa).

You want to find a sequence of operations, such that they make all the blocks having the same color. You don't have to minimize the number of operations, but it should not exceed $$$3 \cdot n$$$. If it is impossible to find such a sequence of operations, you need to report it.

## Input Format
The first line contains one integer $$$n$$$ ($$$2 \le n \le 200$$$) — the number of blocks.

The second line contains one string $$$s$$$ consisting of $$$n$$$ characters, each character is either "W" or "B". If the $$$i$$$-th character is "W", then the $$$i$$$-th block is white. If the $$$i$$$-th character is "B", then the $$$i$$$-th block is black.

## Output Format
If it is impossible to make all the blocks having the same color, print $$$-1$$$.

Otherwise, print an integer $$$k$$$ ($$$0 \le k \le 3 \cdot n$$$) — the number of operations. Then print $$$k$$$ integers $$$p_1, p_2, \dots, p_k$$$ $$$(1 \le p_j \le n - 1)$$$, where $$$p_j$$$ is the position of the left block in the pair of blocks that should be affected by the $$$j$$$-th operation.

If there are multiple answers, print any of them.

## Examples
```input
8
BWWWWWWB
```
```output
3
6 2 4
```
-----
```input
4
BWBB
```
```output
-1
```
-----
```input
5
WWWWW
```
```output
0
```
-----
```input
3
BWB
```
```output
2
2 1
```

## Note
In the first example, it is possible to make all blocks black in $$$3$$$ operations. Start with changing blocks $$$6$$$ and $$$7$$$, so the sequence is "BWWWWBBB". Then change blocks $$$2$$$ and $$$3$$$, so the sequence is "BBBWWBB". And finally, change blocks $$$4$$$ and $$$5$$$, so all blocks are black.

It is impossible to make all colors equal in the second example.

All blocks are already white in the third example.

In the fourth example it is possible to make all blocks white in two operations: first operation is to change blocks $$$2$$$ and $$$3$$$ (so the sequence is "BBW"), and then change blocks $$$1$$$ and $$$2$$$ (so all blocks are white).

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
At first, let's define function $$$f(x)$$$ as follows: $$$$$$ \begin{matrix} f(x) & = & \left\{ \begin{matrix} \frac{x}{2} & \mbox{if } x \text{ is even} \\ x - 1 & \mbox{otherwise } \end{matrix} \right. \end{matrix} $$$$$$

We can see that if we choose some value $$$v$$$ and will apply function $$$f$$$ to it, then apply $$$f$$$ to $$$f(v)$$$, and so on, we'll eventually get $$$1$$$. Let's write down all values we get in this process in a list and denote this list as $$$path(v)$$$. For example, $$$path(1) = [1]$$$, $$$path(15) = [15, 14, 7, 6, 3, 2, 1]$$$, $$$path(32) = [32, 16, 8, 4, 2, 1]$$$.

Let's write all lists $$$path(x)$$$ for every $$$x$$$ from $$$1$$$ to $$$n$$$. The question is next: what is the maximum value $$$y$$$ such that $$$y$$$ is contained in at least $$$k$$$ different lists $$$path(x)$$$?

Formally speaking, you need to find maximum $$$y$$$ such that $$$\left| \{ x ~|~ 1 \le x \le n, y \in path(x) \} \right| \ge k$$$.

## Input Format
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 10^{18}$$$).

## Output Format
Print the only integer — the maximum value that is contained in at least $$$k$$$ paths.

## Examples
```input
11 3
```
```output
5
```
-----
```input
11 6
```
```output
4
```
-----
```input
20 20
```
```output
1
```
-----
```input
14 5
```
```output
6
```
-----
```input
1000000 100
```
```output
31248
```

## Note
In the first example, the answer is $$$5$$$, since $$$5$$$ occurs in $$$path(5)$$$, $$$path(10)$$$ and $$$path(11)$$$.

In the second example, the answer is $$$4$$$, since $$$4$$$ occurs in $$$path(4)$$$, $$$path(5)$$$, $$$path(8)$$$, $$$path(9)$$$, $$$path(10)$$$ and $$$path(11)$$$.

In the third example $$$n = k$$$, so the answer is $$$1$$$, since $$$1$$$ is the only number occuring in all paths for integers from $$$1$$$ to $$$20$$$.

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

# Problem
A sequence $$$a = [a_1, a_2, \ldots, a_l]$$$ of length $$$l$$$ has an ascent if there exists a pair of indices $$$(i, j)$$$ such that $$$1 \le i < j \le l$$$ and $$$a_i < a_j$$$. For example, the sequence $$$[0, 2, 0, 2, 0]$$$ has an ascent because of the pair $$$(1, 4)$$$, but the sequence $$$[4, 3, 3, 3, 1]$$$ doesn't have an ascent.

Let's call a concatenation of sequences $$$p$$$ and $$$q$$$ the sequence that is obtained by writing down sequences $$$p$$$ and $$$q$$$ one right after another without changing the order. For example, the concatenation of the $$$[0, 2, 0, 2, 0]$$$ and $$$[4, 3, 3, 3, 1]$$$ is the sequence $$$[0, 2, 0, 2, 0, 4, 3, 3, 3, 1]$$$. The concatenation of sequences $$$p$$$ and $$$q$$$ is denoted as $$$p+q$$$.

Gyeonggeun thinks that sequences with ascents bring luck. Therefore, he wants to make many such sequences for the new year. Gyeonggeun has $$$n$$$ sequences $$$s_1, s_2, \ldots, s_n$$$ which may have different lengths.

Gyeonggeun will consider all $$$n^2$$$ pairs of sequences $$$s_x$$$ and $$$s_y$$$ ($$$1 \le x, y \le n$$$), and will check if its concatenation $$$s_x + s_y$$$ has an ascent. Note that he may select the same sequence twice, and the order of selection matters.

Please count the number of pairs ($$$x, y$$$) of sequences $$$s_1, s_2, \ldots, s_n$$$ whose concatenation $$$s_x + s_y$$$ contains an ascent.

## Input Format
The first line contains the number $$$n$$$ ($$$1 \le n \le 100\,000$$$) denoting the number of sequences.

The next $$$n$$$ lines contain the number $$$l_i$$$ ($$$1 \le l_i$$$) denoting the length of $$$s_i$$$, followed by $$$l_i$$$ integers $$$s_{i, 1}, s_{i, 2}, \ldots, s_{i, l_i}$$$ ($$$0 \le s_{i, j} \le 10^6$$$) denoting the sequence $$$s_i$$$.

It is guaranteed that the sum of all $$$l_i$$$ does not exceed $$$100\,000$$$.

## Output Format
Print a single integer, the number of pairs of sequences whose concatenation has an ascent.

## Examples
```input
5
1 1
1 1
1 2
1 4
1 3
```
```output
9
```
-----
```input
3
4 2 0 2 0
6 9 9 8 8 7 7
1 6
```
```output
7
```
-----
```input
10
3 62 24 39
1 17
1 99
1 60
1 64
1 30
2 79 29
2 20 73
2 85 37
1 100
```
```output
72
```

## Note
For the first example, the following $$$9$$$ arrays have an ascent: $$$[1, 2], [1, 2], [1, 3], [1, 3], [1, 4], [1, 4], [2, 3], [2, 4], [3, 4]$$$. Arrays with the same contents are counted as their occurences.

Now solve the problem and return the code.