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

# Problem
You are given a tree of $$$n$$$ nodes. The tree is rooted at node $$$1$$$, which is not considered as a leaf regardless of its degree.

Each leaf of the tree has one of the two colors: red or blue. Leaf node $$$v$$$ initially has color $$$s_{v}$$$.

The color of each of the internal nodes (including the root) is determined as follows.

- Let $$$b$$$ be the number of blue immediate children, and $$$r$$$ be the number of red immediate children of a given vertex.
- Then the color of this vertex is blue if and only if $$$b - r \ge k$$$, otherwise red.

Integer $$$k$$$ is a parameter that is same for all the nodes.

You need to handle the following types of queries:

- 1 v: print the color of node $$$v$$$;
- 2 v c: change the color of leaf $$$v$$$ to $$$c$$$ ($$$c = 0$$$ means red, $$$c = 1$$$ means blue);
- 3 h: update the current value of $$$k$$$ to $$$h$$$.

## Input Format
The first line of the input consists of two integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 10^{5}$$$, $$$-n \le k \le n$$$) — the number of nodes and the initial parameter $$$k$$$.

Each of the next $$$n - 1$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u,v \le n$$$), denoting that there is an edge between vertices $$$u$$$ and $$$v$$$.

The next line consists of $$$n$$$ space separated integers — the initial array $$$s$$$ ($$$-1 \le s_i \le 1$$$). $$$s_{i} = 0$$$ means that the color of node $$$i$$$ is red. $$$s_{i} = 1$$$ means that the color of node $$$i$$$ is blue. $$$s_{i} = -1$$$ means that the node $$$i$$$ is not a leaf.

The next line contains an integer $$$q$$$ ($$$1 \le q \le 10^5$$$), the number of queries.

$$$q$$$ lines follow, each containing a query in one of the following queries:

- 1 v ($$$1 \le v \le n$$$): print the color of node $$$v$$$;
- 2 v c ($$$1 \le v \le n$$$, $$$c = 0$$$ or $$$c = 1$$$): change the color of leaf $$$v$$$ to $$$c$$$ ($$$c = 0$$$ means red, $$$c = 1$$$ means blue). It is guaranteed that $$$v$$$ is a leaf;
- 3 h ($$$-n \le h \le n$$$): update the current value of $$$k$$$ to $$$h$$$.

## Output Format
For each query of the first type, print $$$0$$$ if the color of vertex $$$v$$$ is red, and $$$1$$$ otherwise.

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

## Note
Figures:(i) The initial tree (ii) The tree after the 3rd query (iii) The tree after the 7th 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 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: 512.0 MB

# Problem
Andrew was very excited to participate in Olympiad of Metropolises. Days flew by quickly, and Andrew is already at the airport, ready to go home. He has $$$n$$$ rubles left, and would like to exchange them to euro and dollar bills. Andrew can mix dollar bills and euro bills in whatever way he wants. The price of one dollar is $$$d$$$ rubles, and one euro costs $$$e$$$ rubles.

Recall that there exist the following dollar bills: $$$1$$$, $$$2$$$, $$$5$$$, $$$10$$$, $$$20$$$, $$$50$$$, $$$100$$$, and the following euro bills — $$$5$$$, $$$10$$$, $$$20$$$, $$$50$$$, $$$100$$$, $$$200$$$ (note that, in this problem we do not consider the $$$500$$$ euro bill, it is hard to find such bills in the currency exchange points). Andrew can buy any combination of bills, and his goal is to minimize the total number of rubles he will have after the exchange.

Help him — write a program that given integers $$$n$$$, $$$e$$$ and $$$d$$$, finds the minimum number of rubles Andrew can get after buying dollar and euro bills.

## Input Format
The first line of the input contains one integer $$$n$$$ ($$$1 \leq n \leq 10^8$$$) — the initial sum in rubles Andrew has.

The second line of the input contains one integer $$$d$$$ ($$$30 \leq d \leq 100$$$) — the price of one dollar in rubles.

The third line of the input contains integer $$$e$$$ ($$$30 \leq e \leq 100$$$) — the price of one euro in rubles.

## Output Format
Output one integer — the minimum number of rubles Andrew can have after buying dollar and euro bills optimally.

## Examples
```input
100
60
70
```
```output
40
```
-----
```input
410
55
70
```
```output
5
```
-----
```input
600
60
70
```
```output
0
```

## Note
In the first example, we can buy just $$$1$$$ dollar because there is no $$$1$$$ euro bill.

In the second example, optimal exchange is to buy $$$5$$$ euro and $$$1$$$ dollar.

In the third example, optimal exchange is to buy $$$10$$$ dollars in one bill.

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

# Problem
There are $$$b$$$ boys and $$$g$$$ girls participating in Olympiad of Metropolises. There will be a board games tournament in the evening and $$$n$$$ participants have accepted the invitation. The organizers do not know how many boys and girls are among them.

Organizers are preparing red badges for girls and blue ones for boys.

Vasya prepared $$$n+1$$$ decks of badges. The $$$i$$$-th (where $$$i$$$ is from $$$0$$$ to $$$n$$$, inclusive) deck contains $$$i$$$ blue badges and $$$n-i$$$ red ones. The total number of badges in any deck is exactly $$$n$$$.

Determine the minimum number of decks among these $$$n+1$$$ that Vasya should take, so that there will be a suitable deck no matter how many girls and boys there will be among the participants of the tournament.

## Input Format
The first line contains an integer $$$b$$$ ($$$1 \le b \le 300$$$), the number of boys.

The second line contains an integer $$$g$$$ ($$$1 \le g \le 300$$$), the number of girls.

The third line contains an integer $$$n$$$ ($$$1 \le n \le b + g$$$), the number of the board games tournament participants.

## Output Format
Output the only integer, the minimum number of badge decks that Vasya could take.

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

## Note
In the first example, each of 4 decks should be taken: (0 blue, 3 red), (1 blue, 2 red), (2 blue, 1 red), (3 blue, 0 red).

In the second example, 4 decks should be taken: (2 blue, 3 red), (3 blue, 2 red), (4 blue, 1 red), (5 blue, 0 red). Piles (0 blue, 5 red) and (1 blue, 4 red) can not be used.

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

# Problem
Petya's friends made him a birthday present — a bracket sequence. Petya was quite disappointed with his gift, because he dreamed of correct bracket sequence, yet he told his friends nothing about his dreams and decided to fix present himself.

To make everything right, Petya is going to move at most one bracket from its original place in the sequence to any other position. Reversing the bracket (e.g. turning "(" into ")" or vice versa) isn't allowed.

We remind that bracket sequence $$$s$$$ is called correct if:

- $$$s$$$ is empty;
- $$$s$$$ is equal to "($$$t$$$)", where $$$t$$$ is correct bracket sequence;
- $$$s$$$ is equal to $$$t_1 t_2$$$, i.e. concatenation of $$$t_1$$$ and $$$t_2$$$, where $$$t_1$$$ and $$$t_2$$$ are correct bracket sequences.

For example, "(()())", "()" are correct, while ")(" and "())" are not. Help Petya to fix his birthday present and understand whether he can move one bracket so that the sequence becomes correct.

## Input Format
First of line of input contains a single number $$$n$$$ ($$$1 \leq n \leq 200\,000$$$) — length of the sequence which Petya received for his birthday.

Second line of the input contains bracket sequence of length $$$n$$$, containing symbols "(" and ")".

## Output Format
Print "Yes" if Petya can make his sequence correct moving at most one bracket. Otherwise print "No".

## Examples
```input
2
)(
```
```output
Yes
```
-----
```input
3
(()
```
```output
No
```
-----
```input
2
()
```
```output
Yes
```
-----
```input
10
)))))(((((
```
```output
No
```

## Note
In the first example, Petya can move first bracket to the end, thus turning the sequence into "()", which is correct bracket sequence.

In the second example, there is no way to move at most one bracket so that the sequence becomes correct.

In the third example, the sequence is already correct and there's no need to move brackets.

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

# Problem
The new pedestrian zone in Moscow city center consists of $$$n$$$ squares connected with each other by $$$n - 1$$$ footpaths. We define a simple path as a sequence of squares such that no square appears in this sequence twice and any two adjacent squares in this sequence are directly connected with a footpath. The size of a simple path is the number of squares in it. The footpaths are designed in a such a way that there is exactly one simple path between any pair of different squares.

During preparations for Moscow City Day the city council decided to renew ground tiles on all $$$n$$$ squares. There are $$$k$$$ tile types of different colors, numbered from $$$1$$$ to $$$k$$$. For each square exactly one tile type must be selected and then used to cover this square surface. To make walking through the city center more fascinating, it was decided to select tiles types for each square in such a way that any possible simple path of size exactly $$$k$$$ contains squares with all $$$k$$$ possible tile colors.

You need to find out whether it is possible to place the tiles this way or not.

## Input Format
The first line contains two integers $$$n$$$, $$$k$$$ ($$$2 \le k \le n \le 200\,000$$$) — the number of squares in the new pedestrian zone, the number of different tile colors.

Each of the following $$$n - 1$$$ lines contains two integers $$$v_i$$$ and $$$u_i$$$ ($$$1 \le v_i, u_i \le n$$$) — numbers of the squares connected by the corresponding road.

It's guaranteed, that it's possible to go from any square to any other square, moreover there is exactly one such simple path.

## Output Format
Print "Yes" if it is possible to assign tile colors this way and "No" otherwise.

In case your answer is "Yes", print $$$n$$$ integers from $$$1$$$ to $$$k$$$ each, the color of the tile for every square.

## Examples
```input
7 4
1 3
2 3
3 4
4 5
5 6
5 7
```
```output
Yes
1 1 2 3 4 1 1
```
-----
```input
7 3
1 3
2 3
3 4
4 5
5 6
5 7
```
```output
No
```

## Note
The following pictures illustrate the pedestrian zone in first and second examples. The second picture also shows one possible distribution of colors among the squares for $$$k = 4$$$.

Now solve the problem and return the code.