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

# Problem
You are given an acyclic directed graph, consisting of $$$n$$$ vertices and $$$m$$$ edges. The graph contains no multiple edges and no self-loops.

The vertex is called a source if it has no incoming edges. The vertex is called a sink if it has no outgoing edges. These definitions imply that some vertices can be both source and sink.

The number of sources in the given graph is equal to the number of sinks in it, and each of these numbers doesn't exceed $$$20$$$.

The following algorithm is applied to the graph:

1. if the graph has no sources and sinks then quit;
2. choose arbitrary source $$$s$$$, arbitrary sink $$$t$$$, add an edge from $$$t$$$ to $$$s$$$ to the graph and go to step $$$1$$$ (that operation pops $$$s$$$ out of sources and $$$t$$$ out of sinks). Note that $$$s$$$ and $$$t$$$ may be the same vertex, then a self-loop is added.

At the end you check if the graph becomes strongly connected (that is, any vertex is reachable from any other vertex).

Your task is to check that the graph becomes strongly connected no matter the choice of sources and sinks on the second step of the algorithm.

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

Each of the next $$$m$$$ lines contains two integers $$$v_i, u_i$$$ ($$$1 \le v_i, u_i \le n$$$, $$$v_i \ne u_i$$$) — the description of the $$$i$$$-th edge of the original graph.

It is guaranteed that the number of sources and the number of sinks in the graph are the same and they don't exceed $$$20$$$. It is guaranteed that the given graph contains no multiple edges. It is guaranteed that the graph contains no cycles.

## Output Format
Print "YES" if the graph becomes strongly connected no matter the choice of sources and sinks on the second step of the algorithm. Otherwise print "NO".

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

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

# Problem
You are given two arrays $$$a_0, a_1, \ldots, a_{n - 1}$$$ and $$$b_0, b_1, \ldots, b_{m-1}$$$, and an integer $$$c$$$.

Compute the following sum:

$$$$$$\sum_{i=0}^{n-1} \sum_{j=0}^{m-1} a_i b_j c^{i^2\,j^3}$$$$$$

Since it's value can be really large, print it modulo $$$490019$$$.

## Input Format
First line contains three integers $$$n$$$, $$$m$$$ and $$$c$$$ ($$$1 \le n, m \le 100\,000$$$, $$$1 \le c < 490019$$$).

Next line contains exactly $$$n$$$ integers $$$a_i$$$ and defines the array $$$a$$$ ($$$0 \le a_i \le 1000$$$).

Last line contains exactly $$$m$$$ integers $$$b_i$$$ and defines the array $$$b$$$ ($$$0 \le b_i \le 1000$$$).

## Output Format
Print one integer — value of the sum modulo $$$490019$$$.

## Examples
```input
2 2 3
0 1
0 1
```
```output
3
```
-----
```input
3 4 1
1 1 1
1 1 1 1
```
```output
12
```
-----
```input
2 3 3
1 2
3 4 5
```
```output
65652
```

## Note
In the first example, the only non-zero summand corresponds to $$$i = 1$$$, $$$j = 1$$$ and is equal to $$$1 \cdot 1 \cdot 3^1 = 3$$$.

In the second example, all summands are equal to $$$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 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 unlimited number of coins with values $$$1, 2, \ldots, n$$$. You want to select some set of coins having the total value of $$$S$$$.

It is allowed to have multiple coins with the same value in the set. What is the minimum number of coins required to get sum $$$S$$$?

## Input Format
The only line of the input contains two integers $$$n$$$ and $$$S$$$ ($$$1 \le n \le 100\,000$$$, $$$1 \le S \le 10^9$$$)

## Output Format
Print exactly one integer — the minimum number of coins required to obtain sum $$$S$$$.

## Examples
```input
5 11
```
```output
3
```
-----
```input
6 16
```
```output
3
```

## Note
In the first example, some of the possible ways to get sum $$$11$$$ with $$$3$$$ coins are:

- $$$(3, 4, 4)$$$
- $$$(2, 4, 5)$$$
- $$$(1, 5, 5)$$$
- $$$(3, 3, 5)$$$

It is impossible to get sum $$$11$$$ with less than $$$3$$$ coins.

In the second example, some of the possible ways to get sum $$$16$$$ with $$$3$$$ coins are:

- $$$(5, 5, 6)$$$
- $$$(4, 6, 6)$$$

It is impossible to get sum $$$16$$$ with less than $$$3$$$ coins.

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 came to the exhibition and one exhibit has drawn your attention. It consists of $$$n$$$ stacks of blocks, where the $$$i$$$-th stack consists of $$$a_i$$$ blocks resting on the surface.

The height of the exhibit is equal to $$$m$$$. Consequently, the number of blocks in each stack is less than or equal to $$$m$$$.

There is a camera on the ceiling that sees the top view of the blocks and a camera on the right wall that sees the side view of the blocks.

Find the maximum number of blocks you can remove such that the views for both the cameras would not change.

Note, that while originally all blocks are stacked on the floor, it is not required for them to stay connected to the floor after some blocks are removed. There is no gravity in the whole exhibition, so no block would fall down, even if the block underneath is removed. It is not allowed to move blocks by hand either.

## Input Format
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 100\,000$$$, $$$1 \le m \le 10^9$$$) — the number of stacks and the height of the exhibit.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le m$$$) — the number of blocks in each stack from left to right.

## Output Format
Print exactly one integer — the maximum number of blocks that can be removed.

## Examples
```input
5 6
3 3 3 3 3
```
```output
10
```
-----
```input
3 5
1 2 4
```
```output
3
```
-----
```input
5 5
2 3 1 4 4
```
```output
9
```
-----
```input
1 1000
548
```
```output
0
```
-----
```input
3 3
3 1 1
```
```output
1
```

## Note
The following pictures illustrate the first example and its possible solution.

Blue cells indicate removed blocks. There are $$$10$$$ blue cells, so the answer is $$$10$$$.

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

# Problem
You are given an integer array $$$a_1, a_2, \ldots, a_n$$$.

The array $$$b$$$ is called to be a subsequence of $$$a$$$ if it is possible to remove some elements from $$$a$$$ to get $$$b$$$.

Array $$$b_1, b_2, \ldots, b_k$$$ is called to be good if it is not empty and for every $$$i$$$ ($$$1 \le i \le k$$$) $$$b_i$$$ is divisible by $$$i$$$.

Find the number of good subsequences in $$$a$$$ modulo $$$10^9 + 7$$$.

Two subsequences are considered different if index sets of numbers included in them are different. That is, the values ​of the elements ​do not matter in the comparison of subsequences. In particular, the array $$$a$$$ has exactly $$$2^n - 1$$$ different subsequences (excluding an empty subsequence).

## Input Format
The first line contains an integer $$$n$$$ ($$$1 \le n \le 100\,000$$$) — the length of the array $$$a$$$.

The next line contains integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^6$$$).

## Output Format
Print exactly one integer — the number of good subsequences taken modulo $$$10^9 + 7$$$.

## Examples
```input
2
1 2
```
```output
3
```
-----
```input
5
2 2 1 22 14
```
```output
13
```

## Note
In the first example, all three non-empty possible subsequences are good: $$$\{1\}$$$, $$$\{1, 2\}$$$, $$$\{2\}$$$

In the second example, the possible good subsequences are: $$$\{2\}$$$, $$$\{2, 2\}$$$, $$$\{2, 22\}$$$, $$$\{2, 14\}$$$, $$$\{2\}$$$, $$$\{2, 22\}$$$, $$$\{2, 14\}$$$, $$$\{1\}$$$, $$$\{1, 22\}$$$, $$$\{1, 14\}$$$, $$$\{22\}$$$, $$$\{22, 14\}$$$, $$$\{14\}$$$.

Note, that some subsequences are listed more than once, since they occur in the original array multiple times.

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
Vasya has got an undirected graph consisting of $$$n$$$ vertices and $$$m$$$ edges. This graph doesn't contain any self-loops or multiple edges. Self-loop is an edge connecting a vertex to itself. Multiple edges are a pair of edges such that they connect the same pair of vertices. Since the graph is undirected, the pair of edges $$$(1, 2)$$$ and $$$(2, 1)$$$ is considered to be multiple edges. Isolated vertex of the graph is a vertex such that there is no edge connecting this vertex to any other vertex.

Vasya wants to know the minimum and maximum possible number of isolated vertices in an undirected graph consisting of $$$n$$$ vertices and $$$m$$$ edges.

## Input Format
The only line contains two integers $$$n$$$ and $$$m~(1 \le n \le 10^5, 0 \le m \le \frac{n (n - 1)}{2})$$$.

It is guaranteed that there exists a graph without any self-loops or multiple edges with such number of vertices and edges.

## Output Format
In the only line print two numbers $$$min$$$ and $$$max$$$ — the minimum and maximum number of isolated vertices, respectively.

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

## Note
In the first example it is possible to construct a graph with $$$0$$$ isolated vertices: for example, it should contain edges $$$(1, 2)$$$ and $$$(3, 4)$$$. To get one isolated vertex, we may construct a graph with edges $$$(1, 2)$$$ and $$$(1, 3)$$$.

In the second example the graph will always contain exactly one isolated vertex.

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 is a toy building consisting of $$$n$$$ towers. Each tower consists of several cubes standing on each other. The $$$i$$$-th tower consists of $$$h_i$$$ cubes, so it has height $$$h_i$$$.

Let's define operation slice on some height $$$H$$$ as following: for each tower $$$i$$$, if its height is greater than $$$H$$$, then remove some top cubes to make tower's height equal to $$$H$$$. Cost of one "slice" equals to the total number of removed cubes from all towers.

Let's name slice as good one if its cost is lower or equal to $$$k$$$ ($$$k \ge n$$$).

Calculate the minimum number of good slices you have to do to make all towers have the same height. Of course, it is always possible to make it so.

## Input Format
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$n \le k \le 10^9$$$) — the number of towers and the restriction on slices, respectively.

The second line contains $$$n$$$ space separated integers $$$h_1, h_2, \dots, h_n$$$ ($$$1 \le h_i \le 2 \cdot 10^5$$$) — the initial heights of towers.

## Output Format
Print one integer — the minimum number of good slices you have to do to make all towers have the same heigth.

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

## Note
In the first example it's optimal to make $$$2$$$ slices. The first slice is on height $$$2$$$ (its cost is $$$3$$$), and the second one is on height $$$1$$$ (its cost is $$$4$$$).

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 stumbled upon a new kind of chess puzzles. The chessboard you are given is not necesserily $$$8 \times 8$$$, but it still is $$$N \times N$$$. Each square has some number written on it, all the numbers are from $$$1$$$ to $$$N^2$$$ and all the numbers are pairwise distinct. The $$$j$$$-th square in the $$$i$$$-th row has a number $$$A_{ij}$$$ written on it.

In your chess set you have only three pieces: a knight, a bishop and a rook. At first, you put one of them on the square with the number $$$1$$$ (you can choose which one). Then you want to reach square $$$2$$$ (possibly passing through some other squares in process), then square $$$3$$$ and so on until you reach square $$$N^2$$$. In one step you are allowed to either make a valid move with the current piece or replace it with some other piece. Each square can be visited arbitrary number of times.

A knight can move to a square that is two squares away horizontally and one square vertically, or two squares vertically and one square horizontally. A bishop moves diagonally. A rook moves horizontally or vertically. The move should be performed to a different square from the one a piece is currently standing on.

You want to minimize the number of steps of the whole traversal. Among all the paths to have the same number of steps you want to choose the one with the lowest number of piece replacements.

What is the path you should take to satisfy all conditions?

## Input Format
The first line contains a single integer $$$N$$$ ($$$3 \le N \le 10$$$) — the size of the chessboard.

Each of the next $$$N$$$ lines contains $$$N$$$ integers $$$A_{i1}, A_{i2}, \dots, A_{iN}$$$ ($$$1 \le A_{ij} \le N^2$$$) — the numbers written on the squares of the $$$i$$$-th row of the board.

It is guaranteed that all $$$A_{ij}$$$ are pairwise distinct.

## Output Format
The only line should contain two integers — the number of steps in the best answer and the number of replacement moves in it.

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

## Note
Here are the steps for the first example (the starting piece is a knight):

1. Move to $$$(3, 2)$$$
2. Move to $$$(1, 3)$$$
3. Move to $$$(3, 2)$$$
4. Replace the knight with a rook
5. Move to $$$(3, 1)$$$
6. Move to $$$(3, 3)$$$
7. Move to $$$(3, 2)$$$
8. Move to $$$(2, 2)$$$
9. Move to $$$(2, 3)$$$
10. Move to $$$(2, 1)$$$
11. Move to $$$(1, 1)$$$
12. Move to $$$(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 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
Consider some set of distinct characters $$$A$$$ and some string $$$S$$$, consisting of exactly $$$n$$$ characters, where each character is present in $$$A$$$.

You are given an array of $$$m$$$ integers $$$b$$$ ($$$b_1 < b_2 < \dots < b_m$$$).

You are allowed to perform the following move on the string $$$S$$$:

1. Choose some valid $$$i$$$ and set $$$k = b_i$$$;
2. Take the first $$$k$$$ characters of $$$S = Pr_k$$$;
3. Take the last $$$k$$$ characters of $$$S = Su_k$$$;
4. Substitute the first $$$k$$$ characters of $$$S$$$ with the reversed $$$Su_k$$$;
5. Substitute the last $$$k$$$ characters of $$$S$$$ with the reversed $$$Pr_k$$$.

For example, let's take a look at $$$S =$$$ "abcdefghi" and $$$k = 2$$$. $$$Pr_2 =$$$ "ab", $$$Su_2 =$$$ "hi". Reversed $$$Pr_2 =$$$ "ba", $$$Su_2 =$$$ "ih". Thus, the resulting $$$S$$$ is "ihcdefgba".

The move can be performed arbitrary number of times (possibly zero). Any $$$i$$$ can be selected multiple times over these moves.

Let's call some strings $$$S$$$ and $$$T$$$ equal if and only if there exists such a sequence of moves to transmute string $$$S$$$ to string $$$T$$$. For the above example strings "abcdefghi" and "ihcdefgba" are equal. Also note that this implies $$$S = S$$$.

The task is simple. Count the number of distinct strings.

The answer can be huge enough, so calculate it modulo $$$998244353$$$.

## Input Format
The first line contains three integers $$$n$$$, $$$m$$$ and $$$|A|$$$ ($$$2 \le n \le 10^9$$$, $$$1 \le m \le min(\frac n 2, 2 \cdot 10^5)$$$, $$$1 \le |A| \le 10^9$$$) — the length of the strings, the size of the array $$$b$$$ and the size of the set $$$A$$$, respectively.

The second line contains $$$m$$$ integers $$$b_1, b_2, \dots, b_m$$$ ($$$1 \le b_i \le \frac n 2$$$, $$$b_1 < b_2 < \dots < b_m$$$).

## Output Format
Print a single integer — the number of distinct strings of length $$$n$$$ with characters from set $$$A$$$ modulo $$$998244353$$$.

## Examples
```input
3 1 2
1
```
```output
6
```
-----
```input
9 2 26
2 3
```
```output
150352234
```
-----
```input
12 3 1
2 5 6
```
```output
1
```

## Note
Here are all the distinct strings for the first example. The chosen letters 'a' and 'b' are there just to show that the characters in $$$A$$$ are different.

1. "aaa"
2. "aab" = "baa"
3. "aba"
4. "abb" = "bba"
5. "bab"
6. "bbb"

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

# Problem
You are given a tree with $$$n$$$ vertices; its root is vertex $$$1$$$. Also there is a token, initially placed in the root. You can move the token to other vertices. Let's assume current vertex of token is $$$v$$$, then you make any of the following two possible moves:

- move down to any leaf in subtree of $$$v$$$;
- if vertex $$$v$$$ is a leaf, then move up to the parent no more than $$$k$$$ times. In other words, if $$$h(v)$$$ is the depth of vertex $$$v$$$ (the depth of the root is $$$0$$$), then you can move to vertex $$$to$$$ such that $$$to$$$ is an ancestor of $$$v$$$ and $$$h(v) - k \le h(to)$$$.

Consider that root is not a leaf (even if its degree is $$$1$$$). Calculate the maximum number of different leaves you can visit during one sequence of moves.

## Input Format
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k < n \le 10^6$$$) — the number of vertices in the tree and the restriction on moving up, respectively.

The second line contains $$$n - 1$$$ integers $$$p_2, p_3, \dots, p_n$$$, where $$$p_i$$$ is the parent of vertex $$$i$$$.

It is guaranteed that the input represents a valid tree, rooted at $$$1$$$.

## Output Format
Print one integer — the maximum possible number of different leaves you can visit.

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

## Note
The graph from the first example:

One of the optimal ways is the next one: $$$1 \rightarrow 2 \rightarrow 1 \rightarrow 5 \rightarrow 3 \rightarrow 7 \rightarrow 4 \rightarrow 6$$$.

The graph from the second example:

One of the optimal ways is the next one: $$$1 \rightarrow 7 \rightarrow 5 \rightarrow 8$$$. Note that there is no way to move from $$$6$$$ to $$$7$$$ or $$$8$$$ and vice versa.

Now solve the problem and return the code.