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
You have a simple undirected graph consisting of $$$n$$$ vertices and $$$m$$$ edges. The graph doesn't contain self-loops, there is at most one edge between a pair of vertices. The given graph can be disconnected.

Let's make a definition.

Let $$$v_1$$$ and $$$v_2$$$ be two some nonempty subsets of vertices that do not intersect. Let $$$f(v_{1}, v_{2})$$$ be true if and only if all the conditions are satisfied:

1. There are no edges with both endpoints in vertex set $$$v_1$$$.
2. There are no edges with both endpoints in vertex set $$$v_2$$$.
3. For every two vertices $$$x$$$ and $$$y$$$ such that $$$x$$$ is in $$$v_1$$$ and $$$y$$$ is in $$$v_2$$$, there is an edge between $$$x$$$ and $$$y$$$.

Create three vertex sets ($$$v_{1}$$$, $$$v_{2}$$$, $$$v_{3}$$$) which satisfy the conditions below;

1. All vertex sets should not be empty.
2. Each vertex should be assigned to only one vertex set.
3. $$$f(v_{1}, v_{2})$$$, $$$f(v_{2}, v_{3})$$$, $$$f(v_{3}, v_{1})$$$ are all true.

Is it possible to create such three vertex sets? If it's possible, print matching vertex set for each vertex.

## Input Format
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$3 \le n \le 10^{5}$$$, $$$0 \le m \le \text{min}(3 \cdot 10^{5}, \frac{n(n-1)}{2})$$$) — the number of vertices and edges in the graph.

The $$$i$$$-th of the next $$$m$$$ lines contains two integers $$$a_{i}$$$ and $$$b_{i}$$$ ($$$1 \le a_{i} \lt b_{i} \le n$$$) — it means there is an edge between $$$a_{i}$$$ and $$$b_{i}$$$. The graph doesn't contain self-loops, there is at most one edge between a pair of vertices. The given graph can be disconnected.

## Output Format
If the answer exists, print $$$n$$$ integers. $$$i$$$-th integer means the vertex set number (from $$$1$$$ to $$$3$$$) of $$$i$$$-th vertex. Otherwise, print $$$-1$$$.

If there are multiple answers, print any.

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

## Note
In the first example, if $$$v_{1} = \{ 1 \}$$$, $$$v_{2} = \{ 2, 3 \}$$$, and $$$v_{3} = \{ 4, 5, 6 \}$$$ then vertex sets will satisfy all conditions. But you can assign vertices to vertex sets in a different way; Other answers like "2 3 3 1 1 1" will be accepted as well.

In the second example, it's impossible to make such vertex sets.

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
You have $$$n \times n$$$ square grid and an integer $$$k$$$. Put an integer in each cell while satisfying the conditions below.

- All numbers in the grid should be between $$$1$$$ and $$$k$$$ inclusive.
- Minimum number of the $$$i$$$-th row is $$$1$$$ ($$$1 \le i \le n$$$).
- Minimum number of the $$$j$$$-th column is $$$1$$$ ($$$1 \le j \le n$$$).

Find the number of ways to put integers in the grid. Since the answer can be very large, find the answer modulo $$$(10^{9} + 7)$$$.

These are the examples of valid and invalid grid when $$$n=k=2$$$.

## Input Format
The only line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 250$$$, $$$1 \le k \le 10^{9}$$$).

## Output Format
Print the answer modulo $$$(10^{9} + 7)$$$.

## Examples
```input
2 2
```
```output
7
```
-----
```input
123 456789
```
```output
689974806
```

## Note
In the first example, following $$$7$$$ cases are possible.

In the second example, make sure you print the answer modulo $$$(10^{9} + 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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
You have an integer $$$n$$$. Let's define following tree generation as McDic's generation:

1. Make a complete and full binary tree of $$$2^{n} - 1$$$ vertices. Complete and full binary tree means a tree that exactly one vertex is a root, all leaves have the same depth (distance from the root), and all non-leaf nodes have exactly two child nodes.
2. Select a non-root vertex $$$v$$$ from that binary tree.
3. Remove $$$v$$$ from tree and make new edges between $$$v$$$'s parent and $$$v$$$'s direct children. If $$$v$$$ has no children, then no new edges will be made.

You have a tree. Determine if this tree can be made by McDic's generation. If yes, then find the parent vertex of removed vertex in tree.

## Input Format
The first line contains integer $$$n$$$ ($$$2 \le n \le 17$$$).

The $$$i$$$-th of the next $$$2^{n} - 3$$$ lines contains two integers $$$a_{i}$$$ and $$$b_{i}$$$ ($$$1 \le a_{i} \lt b_{i} \le 2^{n} - 2$$$) — meaning there is an edge between $$$a_{i}$$$ and $$$b_{i}$$$. It is guaranteed that the given edges form a tree.

## Output Format
Print two lines.

In the first line, print a single integer — the number of answers. If given tree cannot be made by McDic's generation, then print $$$0$$$.

In the second line, print all possible answers in ascending order, separated by spaces. If the given tree cannot be made by McDic's generation, then don't print anything.

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

## Note
In the first example, $$$3$$$ is the only possible answer.

In the second example, there are $$$2$$$ possible answers.

In the third example, the tree can't be generated by McDic's generation.

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 string $$$s$$$ consisting of lowercase Latin letters and $$$q$$$ queries for this string.

Recall that the substring $$$s[l; r]$$$ of the string $$$s$$$ is the string $$$s_l s_{l + 1} \dots s_r$$$. For example, the substrings of "codeforces" are "code", "force", "f", "for", but not "coder" and "top".

There are two types of queries:

- $$$1~ pos~ c$$$ ($$$1 \le pos \le |s|$$$, $$$c$$$ is lowercase Latin letter): replace $$$s_{pos}$$$ with $$$c$$$ (set $$$s_{pos} := c$$$);
- $$$2~ l~ r$$$ ($$$1 \le l \le r \le |s|$$$): calculate the number of distinct characters in the substring $$$s[l; r]$$$.

## Input Format
The first line of the input contains one string $$$s$$$ consisting of no more than $$$10^5$$$ lowercase Latin letters.

The second line of the input contains one integer $$$q$$$ ($$$1 \le q \le 10^5$$$) — the number of queries.

The next $$$q$$$ lines contain queries, one per line. Each query is given in the format described in the problem statement. It is guaranteed that there is at least one query of the second type.

## Output Format
For each query of the second type print the answer for it — the number of distinct characters in the required substring in this query.

## Examples
```input
abacaba
5
2 1 4
1 4 b
1 5 b
2 4 6
2 1 7
```
```output
3
1
2
```
-----
```input
dfcbbcfeeedbaea
15
1 6 e
1 4 b
2 6 14
1 7 b
1 12 c
2 6 8
2 1 6
1 7 c
1 2 f
1 10 a
2 7 9
1 10 a
1 14 b
1 1 f
2 1 11
```
```output
5
2
5
2
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 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 string $$$s$$$ consisting only of first $$$20$$$ lowercase Latin letters ('a', 'b', ..., 't').

Recall that the substring $$$s[l; r]$$$ of the string $$$s$$$ is the string $$$s_l s_{l + 1} \dots s_r$$$. For example, the substrings of "codeforces" are "code", "force", "f", "for", but not "coder" and "top".

You can perform the following operation no more than once: choose some substring $$$s[l; r]$$$ and reverse it (i.e. the string $$$s_l s_{l + 1} \dots s_r$$$ becomes $$$s_r s_{r - 1} \dots s_l$$$).

Your goal is to maximize the length of the maximum substring of $$$s$$$ consisting of distinct (i.e. unique) characters.

The string consists of distinct characters if no character in this string appears more than once. For example, strings "abcde", "arctg" and "minecraft" consist of distinct characters but strings "codeforces", "abacaba" do not consist of distinct characters.

## Input Format
The only line of the input contains one string $$$s$$$ consisting of no more than $$$10^6$$$ characters 'a', 'b', ..., 't' (first $$$20$$$ lowercase Latin letters).

## Output Format
Print one integer — the maximum possible length of the maximum substring of $$$s$$$ consisting of distinct characters after reversing no more than one its substring.

## Examples
```input
abacaba
```
```output
3
```
-----
```input
abcdecdf
```
```output
6
```
-----
```input
aabbcc
```
```output
3
```
-----
```input
abcdeefc
```
```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 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: 0.5 seconds
Memory limit: 256.0 MB

# Problem
Petr stands in line of n people, but he doesn't know exactly which position he occupies. He can say that there are no less than a people standing in front of him and no more than b people standing behind him. Find the number of different positions Petr can occupy.

## Input Format
The only line contains three integers n, a and b (0 ≤ a, b < n ≤ 100).

## Output Format
Print the single number — the number of the sought positions.

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

## Note
The possible positions in the first sample are: 2 and 3 (if we number the positions starting with 1).

In the second sample they are 3, 4 and 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 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 n k-digit integers. You have to rearrange the digits in the integers so that the difference between the largest and the smallest number was minimum. Digits should be rearranged by the same rule in all integers.

## Input Format
The first line contains integers n and k — the number and digit capacity of numbers correspondingly (1 ≤ n, k ≤ 8). Next n lines contain k-digit positive integers. Leading zeroes are allowed both in the initial integers and the integers resulting from the rearranging of digits.

## Output Format
Print a single number: the minimally possible difference between the largest and the smallest number after the digits are rearranged in all integers by the same rule.

## Examples
```input
6 4
5237
2753
7523
5723
5327
2537
```
```output
2700
```
-----
```input
3 3
010
909
012
```
```output
3
```
-----
```input
7 5
50808
36603
37198
44911
29994
42543
50156
```
```output
20522
```

## Note
In the first sample, if we rearrange the digits in numbers as (3,1,4,2), then the 2-nd and the 4-th numbers will equal 5237 and 2537 correspondingly (they will be maximum and minimum for such order of digits).

In the second sample, if we swap the second digits and the first ones, we get integers 100, 99 and 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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
You have three piles of candies: red, green and blue candies:

- the first pile contains only red candies and there are $$$r$$$ candies in it,
- the second pile contains only green candies and there are $$$g$$$ candies in it,
- the third pile contains only blue candies and there are $$$b$$$ candies in it.

Each day Tanya eats exactly two candies of different colors. She is free to choose the colors of eaten candies: the only restriction that she can't eat two candies of the same color in a day.

Find the maximal number of days Tanya can eat candies? Each day she needs to eat exactly two candies.

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

Each test case is given as a separate line of the input. It contains three integers $$$r$$$, $$$g$$$ and $$$b$$$ ($$$1 \le r, g, b \le 10^8$$$) — the number of red, green and blue candies, respectively.

## Output Format
Print $$$t$$$ integers: the $$$i$$$-th printed integer is the answer on the $$$i$$$-th test case in the input.

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

## Note
In the first example, Tanya can eat candies for one day only. She can eat any pair of candies this day because all of them have different colors.

In the second example, Tanya can eat candies for two days. For example, she can eat red and green candies on the first day, and green and blue candies on the second day.

In the third example, Tanya can eat candies for two days. For example, she can eat red and green candies on the first day, and red and blue candies on the second day. Note, that two red candies will remain uneaten.

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 PIN code is a string that consists of exactly $$$4$$$ digits. Examples of possible PIN codes: 7013, 0000 and 0990. Please note that the PIN code can begin with any digit, even with 0.

Polycarp has $$$n$$$ ($$$2 \le n \le 10$$$) bank cards, the PIN code of the $$$i$$$-th card is $$$p_i$$$.

Polycarp has recently read a recommendation that it is better to set different PIN codes on different cards. Thus he wants to change the minimal number of digits in the PIN codes of his cards so that all $$$n$$$ codes would become different.

Formally, in one step, Polycarp picks $$$i$$$-th card ($$$1 \le i \le n$$$), then in its PIN code $$$p_i$$$ selects one position (from $$$1$$$ to $$$4$$$), and changes the digit in this position to any other. He needs to change the minimum number of digits so that all PIN codes become different.

Polycarp quickly solved this problem. Can you solve it?

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

The first line of each of $$$t$$$ test sets contains a single integer $$$n$$$ ($$$2 \le n \le 10$$$) — the number of Polycarp's bank cards. The next $$$n$$$ lines contain the PIN codes $$$p_1, p_2, \dots, p_n$$$ — one per line. The length of each of them is $$$4$$$. All PIN codes consist of digits only.

## Output Format
Print the answers to $$$t$$$ test sets. The answer to each set should consist of a $$$n + 1$$$ lines

In the first line print $$$k$$$ — the least number of changes to make all PIN codes different. In the next $$$n$$$ lines output the changed PIN codes in the order corresponding to their appearance in the input. If there are several optimal answers, print any of them.

## Examples
```input
3
2
1234
0600
2
1337
1337
4
3139
3139
3139
3139
```
```output
0
1234
0600
1
1337
1237
3
3139
3138
3939
6139
```

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
On the well-known testing system MathForces, a draw of $$$n$$$ rating units is arranged. The rating will be distributed according to the following algorithm: if $$$k$$$ participants take part in this event, then the $$$n$$$ rating is evenly distributed between them and rounded to the nearest lower integer, At the end of the drawing, an unused rating may remain — it is not given to any of the participants.

For example, if $$$n = 5$$$ and $$$k = 3$$$, then each participant will recieve an $$$1$$$ rating unit, and also $$$2$$$ rating units will remain unused. If $$$n = 5$$$, and $$$k = 6$$$, then none of the participants will increase their rating.

Vasya participates in this rating draw but does not have information on the total number of participants in this event. Therefore, he wants to know what different values of the rating increment are possible to get as a result of this draw and asks you for help.

For example, if $$$n=5$$$, then the answer is equal to the sequence $$$0, 1, 2, 5$$$. Each of the sequence values (and only them) can be obtained as $$$\lfloor n/k \rfloor$$$ for some positive integer $$$k$$$ (where $$$\lfloor x \rfloor$$$ is the value of $$$x$$$ rounded down): $$$0 = \lfloor 5/7 \rfloor$$$, $$$1 = \lfloor 5/5 \rfloor$$$, $$$2 = \lfloor 5/2 \rfloor$$$, $$$5 = \lfloor 5/1 \rfloor$$$.

Write a program that, for a given $$$n$$$, finds a sequence of all possible rating increments.

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

Each line contains an integer $$$n$$$ ($$$1 \le n \le 10^9$$$) — the total number of the rating units being drawn.

## Output Format
Output the answers for each of $$$t$$$ test cases. Each answer should be contained in two lines.

In the first line print a single integer $$$m$$$ — the number of different rating increment values that Vasya can get.

In the following line print $$$m$$$ integers in ascending order — the values of possible rating increments.

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

Now solve the problem and return the code.