First Round SOI 2022/2023

Overview

Welcome to the first round of the Swiss Olympiad in Informatics! You will find below an overview of what you’ve done so far as well as a few things that you should know before getting started.

Contest ends at 2022-11-30T23:59:59+01:00

CategoryTaskTotalSubtask 1Subtask 2Subtask 3Subtask 4Subtask 5
Junior onlyparagliding‒/100‒/15‒/15‒/15‒/25‒/30
Junior onlyrubiksknob‒/100‒/17‒/16‒/23‒/44
Bothboulders‒/100‒/10‒/25‒/30‒/35
Bothcardgame‒/100‒/20‒/20‒/20‒/20‒/20
Bothpalatinalcrypt‒/100‒/15‒/10‒/25‒/50
Regular onlythermalsprings‒/100‒/20‒/20‒/20‒/40
Regular onlydada‒/100‒/10‒/15‒/20‒/15‒/40
Regular onlytrees‒/100‒/10‒/15‒/75

Tips

You may use any programming language to solve the tasks of the first round. To solve a practical task, you have to design a program, download an input file, run the program on the data in that file, write the results in another file and upload it along with the source code to the website, which will grade your submission and display the number of points that you’ve earned as well as an explanation if you did not get all the possible points. In order to read the data in the input file, make sure that your program either reads directly in that file or redirect the standard input to it (in a terminal running on Linux, Windows or OS X, you can do that by using the command ‘yourprogram < inputfile’, replacing ‘yourprogram’ and ‘inputfile’ by the paths to the actual program and input file). There are also theoretical tasks and a creativity task, about which you will get more information on the dedicated pages. More elaborate explanations about how to solve the tasks of the first round await you on our wiki and our training page. Note that in case you get stuck on the tasks, you can move to next task and try again later: no need to solve them in order.

You should also hear about our workshops! In October and November, we offer workshops in two parts about programming and algorithmics. It’s a great opportunity to learn all you need for the first round and to meet other like-minded participants. Whether you’re a beginner or an experienced programmer, it’s worth it to come. More info and registration here.

Don’t hesitate to contact us at info@soi.ch if you have any question about programming or the tasks.

Rules and Prizes

The first round has two categories: Junior and Regular. You can participate in the Junior category if you are eligible to participate in this year’s edition of SOI as well as the two next ones. If you are eligible as a junior, you can choose to participate in the Junior or in the Regular category or in both.

The top 8 juniors will qualify for our training camp in Sarnen. The second round will be open to the top 20 of the Junior category.

The 16 best regular participants qualify for our camp in Sarnen. The top 40 of the regular round will advance to the second round.

The 3 best juniors and 3 best regular participants shall be rewarded with prizes during the SOI Day in January (if someone is among the 3 best juniors and 3 best regular participants, they win both prizes). Also, we will give the Rainbow Award to the participant who has solved the first round in the Regular category using the most programming languages. The last submission with a nonzero score for each subtask counts.

We wish you good luck, hope you will enjoy solving our tasks and look forward to meeting you at our workshops or at SOI Day.

Paragliding

Mouse Binna has recently become interested in paragliding. She is already planning her next trip and is examining different locations where she could go paragliding. Currently, she is looking at a place range. On a map, she marked various points of interests: places where she could start or land, like peaks, cliffs, valleys etc.

The region Binna is currently looking at can be described as a sequence of NN places on a line, numbered from 00 to N1N - 1 from left to right. The ii-th place is located at position xix_i and its height is hih_i meters. Binna can fly from place ii to place jj if place ii is higher than place jj and also all places in between. Note that place jj can lie before or after place ii.

For each place ii, Mouse Binna would like to know the maximal distance she could fly starting from ii. The distance between two places ii and jj is defined as the absolute difference between their positions: xixj|x_i - x_j|. If, for some place, Binna can not fly to any other place, the maximal distance for this place is 00.

Can you help Binna to calculate for each place the maximal distance she could fly starting from there?

Subtask 1: The Uetliberg (15 points)

As Mouse Binna is not yet very experienced, she would like to start at the Uetliberg, which is a small hill next to Zurich. There is only one starting place and as unexperienced as Binna is, she would like to land on the beginner’s landing place directly below. Thus there are only two places to consider, so N=2N = 2.

Input

The first line contains the number of test cases TT. TT test cases follow in the following format:

  • The first line contains a single integer NN denoting the number of places.
  • The second line consists of NN integers xix_i denoting the position of the ii-th place.
  • The third line consist of NN integers hih_i denoting the height of the ii-th place.

Output

For the ii-th testcase, output a line containing “Case #i:” followed by NN integers, where the jj-th integer is the maximum flight distance if Binna begins at place jj.

Limits

  • T=100T=100.
  • N=2N = 2.
  • 1xi,hi1091 \le x_i, h_i \le 10^{9}.
  • xi<xi+1x_i < x_{i+1}, the places are given in increasing order of position.
  • hihjh_i \neq h_j for iji \neq j, the height of each place is distinct.

Example

Input:

2
2
3 5
10 20
2
0 639
732 554

Output:

Case #0: 0 2
Case #1: 639 0

Comment:

Case #0: We cannot glide from the first place to the second place since its height is lower, thus no trip is possible and the distance is 00. Since the second place is higher than the first we can fly from the second place to the first place, the distance of this trip is 22.

Case #1: Here since the first place is higher than the second we may fly from the first to the second with a distance of 639639 meters, flying over the steep face directly below the take-off site at the Uetliberg. However we cannot fly from the second to the first so the distance is 00.

To submit for this subtask, please log in.

Subtask 2: Paragliding at the Gornergrat (15 Points)

Mouse Binna is now already feeling better. As she was enjoying her view of the Matterhorn from the Gornergrat, a rocky ridge next to Zermatt, she had the idea to paraglide at the Gornergrat. On her way back down, she wrote down a list of possible paragliding places. She was walking only downwards, meaning that in this subtask, each place is lower than the place just before it. Can you compute for her for each place how far she could fly starting from this place?

Limits

  • T=100T=100.
  • 2N30002 \le N \le 3\,000.
  • 1xi,hi1091 \le x_i, h_i \le 10^{9}.
  • xi<xi+1x_i < x_{i+1}, the places are given in increasing order of position.
  • hi>hjh_i > h_j for i<ji < j, the heights of the places are decreasing (this is a special restriction of this subtask).

Input and Output

Same as subtask 1.

Example

Input:

2
5
1 3 6 8 9
8 6 5 2 1
6
0 1430 2870 5310 7590 9340
3089 2819 2582 2210 1770 1604

Output:

Case #0: 8 6 3 1 0
Case #1: 9340 7910 6470 4030 1750 0

Comment:

Case #0: From the first place, we can paraglide down everything until place 4 for a distance of 8 meters.

Case #1: It seems like Binna didn’t walk down the Gornergrat, but took the train instead and just wrote down the different train stations. What a lazy mouse.

To submit for this subtask, please log in.

Subtask 3: Mount Kékes (15 Points)

The International Mouse Olympiad in Informatics 2023 will take place in Hungary, and Mouse Binna managed to qualify. She started looking at the different mountains of Hungary and figured out that for paragliding her best bet would be Mount Kékes. So she started looking at possible places for take-off and landing at Mount Kékes. Mount Kékes has what she calls the “standard mountain shape”. Thus for all cases in this subtask, the heights are first increasing and then decreasing. Formally, in every test case there is an index kk such that h0<<hk1<hk>hk+1>>hn1h_{0}< {\dots} < h_{k - 1} < h_k > h_{k + 1} > {\dots} > h_{n - 1} (note that kk can be 00 or n1n - 1).

Limits

  • T=100T=100.
  • 2N30002 \le N \le 3\,000.
  • 1xi,hi1091 \le x_i, h_i \le 10^{9}.
  • xi<xi+1x_i < x_{i+1}, the places are given in increasing order of position.
  • There is an index kk such that h0<<hk1<hk>hk+1>>hn1h_{0}< {\dots} < h_{k - 1} < h_k > h_{k + 1} > {\dots} > h_{n - 1} (this is a special restriction of this subtask).

Input and Output

Same as subtasks 1 and 2.

Example

Input:

2
6
1 2 6 7 8 9
1 4 5 7 6 2
8
0 957 1370 1981 2873 3001 3651 4781
675 836 949 1014 885 881 730 565

Output:

Case #0: 0 1 5 6 1 0
Case #1: 0 957 1370 2800 1908 1780 1130 0

Comment:

Case #0: From place number 3, all the places are reachable, however, the longest flight can be achieved by flying all to the left until place 0.

Case #1: Did you know that Mount Kékes is only 1014 metres high?

To submit for this subtask, please log in.

Subtask 4: The Mátra Mountain Range (25 points)

Mouse Binna figured out that if she wants to find longer paraglides, she must take into account multiple mountains instead of only a single one. Thus she is now looking at the Mátra mountain range in Hungary. She already wrote down a lot of places to look at. However, this time, there is no real pattern. Can you still help Binna and compute for her how far she can fly from each possible starting point?

Input and Output

Same as subtasks 1, 2 and 3.

Limits

  • T=100T=100.
  • 2N30002 \le N \le 3\,000.
  • 1xi,hi1091 \le x_i, h_i \le 10^{9}.
  • xi<xi+1x_i < x_{i+1}, the places are given in increasing order of position.
  • hihjh_i \neq h_j for iji \neq j, the height of each place is distinct.

Example

Input:

2
5
1 2 3 4 5
5 3 1 2 4
5
1 3 6 8 9
2 1 3 5 4

Output:

Case #0: 4 2 0 1 3
Case #1: 2 0 5 7 0

Comment:

Case #0: The first place has height 5 so we can glide all the way to the last place with height 4, for a distance of 4. From the last place with height 4 we can glide to the second place, for a distance of 3. The other trips may also be shown to be maximal.

Case #1: Note that from the place with index 3 (position 8 and height 5) we may fly to the place with index 0 (position 1 and height 2) for a distance of 7, although a place between them exists with height 3. This is because only the starting height must be greater than all heights between the starting and ending place. The ending height may be lower than a place between the starting and ending place.

To submit for this subtask, please log in.

Subtask 5: All of Hungary (30 points)

Back in Mouseland Binna has a lot of fans. They would love to accompany her on her trip to Hungary. To make it especially interesting, Binna thought that every one of her fans should start from a different location. She still wants to make sure they’re all having as much fun as possible, so each one of their fans should fly the longest possible route.

Can you help her to plan this trip? To keep it simple, she invites only as many fans as there are places to take off from in Hungary. Now she would like to know the total distance they can manage to paraglide through Hungary together. Calculate for each place the longest possible paraglide and tell Binna the combined distance they might achieve.

Input

Same as subtasks 1, 2, 3 and 4.

Output

Output a single number per test case, the combined distance paraglided by all of Binna’s fans.

Limits

  • T=100T=100.
  • 2N1062 \le N \le 10^{6}.
  • 1xi,hi10121 \le x_i, h_i \le 10^{12}. Note that these increased limits lead to large results.
  • xi<xi+1x_i < x_{i+1}, the places are given in increasing order of position.
  • hihjh_i \neq h_j for iji \neq j, the height of each place is distinct.

Example

Input:

3
5
1 2 3 4 5
5 3 1 2 4
5
1 3 6 8 9
2 1 3 5 4
2
0 384403739351
384403739351 0

Output:

Case #0: 10
Case #1: 14
Case #2: 384403739351

Comment:

Case #0: The sample is the same as the first sample from subtask four. The combined distance is calculated as: 4+2+0+1+3=104 + 2 + 0 + 1 + 3 = 10.

Case #1: The sample is the same as the first sample from subtask four. The combined distance is calculated as: 2+0+5+7+0=142 + 0 + 5 + 7 + 0 = 14.

Case #2: Binna’s first fan flies to the second place for a distance of 384403739351mm. Note that in this scenario, Binna’s first fan starts from the surface of the moon while the second fan is waiting in Hungary. Unfortunately, the second fan can’t get to the moon from Hungary, so the total distance remains 384403739351mm.

Note that all but at most 1010 test cases in this subtask also satisfy the limits of the previous subtask. Please be patient, generating the test data can take a while.

To submit for this subtask, please log in.

Don’t hesitate to ask us any question about this task, programming or the website via email (info@soi.ch).

Rubik's Knob

Ernő Rubik is a Hungarian inventor best known for his mechanical puzzles such as the Rubik’s Cube, Rubik’s Magic and Rubik’s Snake. Many of those puzzles have attracted a speed solving community that tries to solve the puzzles as fast as possible.

Mouse Stofl is interested in mastering a lesser known puzzle: the Rubik’s Knob.

The Knob is a round handle that can be rotated. It has an indicator that initially is pointing up. Inside the knob there is a spiral torsion spring that has a charge and tries to push the knob back to its initial position.

The knob can point to one of MM positions in total, numbered from 00 to M1M-1. Initially, the indicator points to position 00.

The spring starts with a charge of 00. The knob can be rotated freely in both directions:

  • right: from position ii to i+1i+1 (for 0iM20\le i\le M-2) or from M1M-1 to 00. This increases the charge by 11.
  • left: from position ii to i1i-1 (for 1iM11\le i\le M-1) or from 00 to M1M-1. This decreases the charge by 11.

We say a rotation is a wind-up step if it goes against the direction of the spring. Formally, this is the case if the absolute value of the charge increases (e.g. from 00 to 11, or from 5-5 to 6-6).

A puzzle for the Rubik’s Knob consists of a sequence x0,x1,,xN1x_{0},x_{1},{\dots},x_{N-1}. The goal is to rotate the knob first to position x0x_{0}, then to position x1x_{1}, etc., until position xN1x_{N-1}.

Subtask 1: Computing the number of wind-ups (17 Points)

By solving some puzzles by hand, Mouse Stofl learned that the time-consuming part are the wind-up steps.

A solution to puzzle x0,x1,,xN1x_{0},x_{1},{\dots},x_{N-1} can be described as a sequence of NN instructions d0,d1,,dN1d_{0},d_{1},{\dots},d_{N-1} where did_i is either “L” or “R” and describes that xix_i should be reached by applying only left (“L”) or only right (“R”) rotations from the previous position.

Given such a solution, compute the number of wind-up steps.

Input

The first line contains the number of test cases TT. TT test cases follow of the following format:

  • The first line contains two integers NN and MM, the length of the puzzle and the number of positions of the knob.
  • The second line contains NN integers x0,x1,,xN1x_{0}, x_{1}, {\dots}, x_{N-1}, where xix_i is the ii-th position the knob needs to be rotated to.
  • The third line contains a string of length NN, where the ii-th character indicates did_i.

Output

For the ii-th testcase, output a line containing “Case #i:” followed by a single integer: the total number of wind-up steps.

Limits

  • T=100T=100.
  • 1N10000001 \le N \le 1\,000\,000.
  • 1M10121 \le M \le 10^{12}.
  • 0xi<M0 \le x_i < M for all 0i<N0\le i<N.
  • di="L"d_i=\mathtt{"L"} or di="R"d_i=\mathtt{"R"} for all 0i<N0\le i<N.

Example

Input:

4
1 10
3
R
1 10
3
L
2 10
3 8
RL
5 1000000000000
0 1 1 9 5
RLRLR

Output:

Case #0: 3
Case #1: 7
Case #2: 5
Case #3: 1999999999991

Comment:

Case #0: All 3 right rotations 010\leadsto 1, 121\leadsto 2 and 232\leadsto 3 are wind-ups.
Case #1: All 7 left rotations 090\leadsto 9, 989\leadsto 8, … , 434\leadsto 3 are wind-ups.
Case #2: The first 3 right rotations are wind-ups, followed by 3 discharges to 0 and two more left rotations which are wind-ups again.
Case #3:
  • from 0 to 0 (right): 0 wind-ups.
  • from 0 to 1 (left): 999999999999 wind-ups.
  • from 1 to 1 (right): 0 wind-ups.
  • from 1 to 9 (left): 999999999992 wind-ups.
  • from 9 to 5 (right) 0 wind-ups (all steps are discharging the spring)

To submit for this subtask, please log in.

Subtask 2: Beginner Puzzles (16 Points)

Being equipped with a way to calculate the cost of solutions, Mouse Stofl now tries to find the optimal way to solve the puzzles.

First, he is starting on beginner puzzles: all positions are given in increasing order.

What is the minimal number of wind-ups required to solve the puzzle?

Input

The first line contains the number of test cases TT. TT test cases follow of the following format:

  • The first line contains two integers NN and MM, the length of the puzzle and the number of positions of the knob.
  • The second line contains NN integers x0,x1,,xN1x_{0}, x_{1}, {\dots}, x_{N-1}, where xix_i is the ii-th position the knob needs to be rotated to.

Output

For the ii-th testcase, output a line containing “Case #i:” followed a single integer: the minimal total number of wind-up steps to solve this puzzle.

Limits

  • T=100T=100.
  • 1N10000001 \le N \le 1\,000\,000.
  • 1M10121 \le M \le 10^{12}.
  • 0xiM10 \le x_i \le M-1 for all 0i<N0\le i<N.
  • 0x0x1x2xN2xN10 \le x_{0}\le x_{1}\le x_{2}\le {\dots} \le x_{N-2} \le x_{N-1}. This is the special restriction for this subtask.

Example

Input:

3
3 5
1 2 3
4 8
1 3 3 7
1 10
9

Output:

Case #0: 3
Case #1: 4
Case #2: 1

Comment:

The optimal sequences are “RRR”, “RRRL” and “L”.

To submit for this subtask, please log in.

Subtask 3: Advanced: Small Puzzles (23 Points)

The advanced puzzle pack contains puzzles with arbitrary positions, but only up to 100100.

Can you help Stofl compute the minimal number of wind-ups to solve those?

Input and Output

Same as subtask 2.

Limits

  • T=100T=100.
  • 1N1001 \le N \le 100. This is the special restriction for this subtask.
  • 1M10121 \le M \le 10^{12}.
  • 0xiM10 \le x_i \le M-1 for all 0i<N0\le i<N.

Example

Input:

2
5 7
4 0 2 4 6
11 3
2 1 2 0 2 1 2 0 2 1 2

Output:

Case #0: 7
Case #1: 6

To submit for this subtask, please log in.

Subtask 4: Expert: Large Puzzles (44 Points)

Finally Stofl thinks he’s able to tackle the expert puzzles: Arbitrary positions and up to 50000005\,000\,000 of them!

Can you help Stofl one more time?

Input and Output

Same as subtasks 2 and 3.

Limits

  • T=100T=100.
  • 1N50000001 \le N \le 5\,000\,000.
  • 1M10121 \le M \le 10^{12}.
  • 0xi<M0 \le x_i < M for all 0i<N0\le i<N.

Note that all but at most 30 test cases in this subtask also satisfy N1000N \le 1000.

To submit for this subtask, please log in.

Don’t hesitate to ask us any question about this task, programming or the website via email (info@soi.ch).

Boulders

While taking a stroll around Kékes, the tallest mountain in Hungary, Mouse Binna has found a nice slope. Unfortunately, there are no boulders on this slope. In order to rectify the situation, Mouse Binna would like to place some boulders in a nice pattern.

The slope is a grid with NN rows and MM columns. Immediately to the left of each row and on top of each column, there is an arbitrarily big supply of boulders. The slope is slanted such that Mouse Binna can easily push boulders to the right or downwards.

More precisely, Mouse Binna can place boulders by executing a sequence of steps. In each step, Mouse Binna can select either a row or a column:

  • If Mouse Binna selects a row, a boulder starts rolling down that row from left to right. The boulder will roll until it reaches the right side of the grid or until it reaches a grid square whose right neighbour is occupied by another boulder.
  • If Mouse Binna selects a column, a boulder starts rolling down that column from top to bottom. The boulder will roll until it reaches the bottom of the grid or until it reaches a grid square whose bottom neighbour is occupied by another boulder.

Note that boulders can never change their direction of movement. As soon as a boulder is moving, Mouse Binna will not be able to stop it until it hits the bottom of the slope or it touches another boulder. Furthermore, once a boulder has stopped rolling, Mouse Binna will not be able to move it again.

Given some nice boulder patterns, determine if Mouse Binna is able to place those patterns on the slope. If it is possible, you should also provide a valid way to place the boulders.

Input

The first line contains the number of test cases TT. TT test cases follow in the following format:

  • the first line contains NN and MM, the number of rows and the number of columns respectively.
  • each of the next NN lines contains a string of characters “.” and “#”, describing a nice pattern of boulders. A character “.” indicates an empty grid square, while a character “#” indicates that a boulder is to be placed on the respective grid square.

Output

For the ii-th test case (zero-based), print a line “Case #i:” followed by the string “No” if Mouse Binna cannot place the boulders in the given nice pattern or “Yes” if Mouse Binna can do it.

In case it is possible, further print a number of lines equal to the number of boulders in the grid. The jj-th such line is either the character “R”, followed by a row index between 00 and N1N-1 or the character “C”, followed by a column index between 00 and M1M-1. Columns are numbered from left to right and rows are numbered from top to bottom. Pushing a boulder down the specified rows and columns in the order printed in the output must result in the given nice pattern.

Note that there can be multiple ways to obtain the given nice pattern, in such a case you can print any one of them.

Limits

In all subtasks: - There are T=100T=100 test cases. - In all but at most 1010 test cases, we have 1NM1001\le N\cdot M\le 100. - In all but at most 2020 test cases, we have 1NM10001\le N\cdot M\le 1\,000. - In all but at most 1010 test cases, we have 1NM100001\le N\cdot M\le 10\,000. - In all testcases, we have 1NM1000001\le N\cdot M\le 100\,000.

Subtask 1 (10 points)

In this subtask, we have the additional constraint that N=1N=1. I.e., there is only a single row. Note that this additional constraint means that it is always possible for Mouse Binna to place the boulders in any given pattern. Therefore, you have to print “Yes” for all test cases.

From N=1N=1, it follows that 1M1000001\le M\le 1'00\,000.

Example

Input:

3
1 1
.
1 1
#
1 4
#.##

Output:

Case #0: Yes
Case #1: Yes
C 0
Case #2: Yes
C 3
R 0
C 0

Comment:

The first line with “3” indicates that there are three test cases.

Case #0: The grid has 11 row and 11 column and Mouse Binna does not have to place any boulders.

Case #1: The grid has 11 row and 11 column, and Mouse Binna has to place a boulder in the single grid square. She can do so by rolling a boulder down column 00. Note that the only other correct output is R 0.
Case #2: The grid has 11 row and 44 columns and Mouse Binna has to place 33 boulders. Note that there are many other correct outputs, for example (R 0, R 0, C 0) or (R 0, C 2, C 0).

Interactive visualization

To submit for this subtask, please log in.

Subtask 2 (25 points)

In this subtask, we have the additional constraint that N=2N=2, i.e., there are exactly two rows. Note that for N=2N=2, there are patterns that Mouse Binna cannot build. For such patterns, you should print “No”.

Example

Input:

3
2 2
.#
##
2 2
#.
..
2 4
#.##
##..

Output:

Case #0: Yes
C 1
C 1
R 1
Case #1: No
Case #2: Yes
R 0
R 0
C 0
C 0
C 1

Comment:

The first line with “3” indicates that there are three test cases.

Case #0: The grid has 22 rows and 22 column and Mouse Binna has to place three boulders. The solution first rolls a boulder down column 11. The boulder stops at the bottom of the grid. It then rolls another boulder down column 11. The boulder is stopped immediately by the other boulder and we fill up column 11 entirely. Finally, Mouse Binna lets a boulder roll down row 11, which is stopped immediately, also by the first boulder.

Case #1: The grid has 22 rows and 22 columns and Mouse Binna has to place one boulder. No matter how Mouse Binna lets a single boulder roll down a row or column, there is no way to place a boulder in the top left square (we could individually fill the three other squares, but not the top left square).
Case #2: The grid has 22 rows and 44 columns and Mouse Binna has to place 55 boulders. She first handles the two boulders at the top right by letting two boulders roll down row 00. Then she handles the leftmost boulders, by letting two boulders roll down column 00. (Note that the order of operations is important, as the fourth boulder closes off row 00.) Finally, she lets a boulder roll down column 11, which handles the final boulder in the middle.

Interactive visualization

To submit for this subtask, please log in.

Subtask 3 (30 points)

Let KK be the number of boulders that we have to place. In this subtask, we have no further constraints on NN and MM, but it is guaranteed that 0K200\le K\le 20.

Example

Input:

3
3 3
.#.
###
...
3 4
##..
.##.
..##
4 5
##...
.####
..#.#
....#

Output:

Case #0: Yes
R 1
R 1
C 1
R 1
Case #1: Yes
R 2
R 2
C 2
R 1
C 1
R 0
Case #2: No

Interactive visualization

To submit for this subtask, please log in.

Subtask 4 (35 points)

In this subtask, there are no further constraints. I.e., we have 1NM1000001\le N\cdot M\le 100\,000 and 0KNM0\le K\le N\cdot M, where KK is the number of boulders we have to place.

To submit for this subtask, please log in.

Don’t hesitate to ask us any question about this task, programming or the website via email (info@soi.ch).

Cardgame

You are playing a card game against Mouse Stofl. Initially, both of you have NN cards. Each card has a number between 00 and 2N12 \cdot N - 1 printed on it, and there is exactly one card of each number. The game has NN turns. In each turn, both players play one of their remaining cards, and the one who played the higher value wins the turn. You already know the order in which Mouse Stofl is going to play his cards.

Subtask 1 (20 Points)

In this subtask, you want to figure out whether you can win all turns, and if yes, in what order you can play your cards to achieve this. If you can’t win all turns, you don’t care how many turns you win.

Input

The first line contains the number of test cases TT. TT test cases follow in the following format:

The first line of the test case contains NN, the number of cards of each player. A second line follows with NN integers a0,,aN1a_{0},\ldots,a_{N-1}, Mouse Stofl’s card values in the order he’s going to be play them. A third line follows with NN integers b0,,bN1b_{0},\ldots,b_{N-1}, your own card values in an arbitrary order.

Output

For the ii-th test case, output a line “Case #i: M”, where M is “No” if you can’t win all turns, otherwise “Yes” followed by NN integers separated by spaces c0cN1c_{0}\ldots c_{N-1}, the values of your cards in the order you’re going to play them.

Limits

There are T=100T=100 test cases. In every test case, 1N10001 \le N \le 1\,000.

Example

Input:

4
3
2 0 3
1 5 4
1
0
1
1
1
0
3
2 1 3
0 5 4

Output:

Case #0: Yes 5 1 4
Case #1: Yes 1
Case #2: No
Case #3: No

Comment:

Case #0: Stofl is going to play 22 in the first turn, 00 in the second turn, and 33 in the third turn. You can win all turns by first playing 55, then 11 and then 44, since 5>25>2, 1>01>0, and 4>34>3. Note that you could also win by swapping the 55 and the 44 from this order. Any winning order is a valid output.
Case #3: There’s no way to play your 00 and not lose that turn.

To submit for this subtask, please log in.

Subtask 2 (20 Points)

In this subtask, you want to lose as many turns as possible. Can you figure out the lowest number of turns you win if you play as badly as possible? Note that you don’t need to print the order you play the cards anymore.

Input

The first line contains the number of test cases TT. TT test cases follow in the following format:

The first line of the test case contains a single integer: NN, the number of cards of each player. A second line follows with NN integers a0,,aN1a_{0},\ldots,a_{N-1}, Mouse Stofl’s card values in the order he’s going to play them. A third line follows with NN integers b0,,bN1b_{0},\ldots,b_{N-1}, your own card values in an arbitrary order.

Output

For the ii-th test case, output a line “Case #i: M”, where MM is the smallest possible number of turns that you can win.

Limits

There are T=100T=100 test cases. In every test case, 1N5000001 \le N \le 500\,000.

Note that all but at most 1010 test cases in this subtask also satisfy 1N100001 \le N \le 10\,000.

Example

Input:

3
3
2 0 3
1 5 4
1
0
1
1
1
0

Output:

Case #0: 2
Case #1: 1
Case #2: 0

To submit for this subtask, please log in.

Subtask 3 (20 Points)

In this subtask, each of your own cards now also has a score attached. A score is a positive integer, and your total score at the end of the game is the sum of the scores of the cards that you played in the turns that you win. Note that Mouse Stofl’s cards don’t have scores in this subtask. Your goal is to maximize your total score.

Input

The first line contains the number of test cases TT. TT test cases follow in the following format:

The first line of the test case contains NN, the number of cards of each player. A second line follows with NN integers a0,,aN1a_{0},\ldots,a_{N-1}, Mouse Stofl’s card values in the order he’s going to play them. A third line follows with NN integers b0,,bN1b_{0},\ldots,b_{N-1}, your own card values in an arbitrary order. A fourth line follows with NN integers s0,,sN1s_{0},\ldots,s_{N-1}, the scores of your cards. (The ii-th card has value bib_i and score sis_i).

Output

For the ii-th test case, output a line “Case #i: M”, where MM is the largest possible total score that you can achieve.

Limits

There are T=100T=100 test cases. In every test case, 1N10001 \le N \le 1\,000. All scores are 1si1000001 \le s_i \le 100\,000.

Example

Input:

2
3
2 0 3
1 5 4
3 2 1
3
1 3 4
0 2 5
11 3 7

Output:

Case #0: 6
Case #1: 10

Comment:

Case #0: As in the example in subtask 1 with the same card values, you can win all turns. This gives you a total score of 1+2+3=61+2+3=6.
Case #1: There’s no way to play your 00 and not lose that turn, so you can’t add those 1111 points in your total score. But you can win the other two turns, giving you a total score of 3+7=103+7=10.

To submit for this subtask, please log in.

Subtask 4 (20 Points)

In this subtask, Mouse Stofl’s cards have scores, and your cards don’t. Your total score at the end of the game is the sum of the scores of the cards that Stofl played in the turns that you win. Your goal is still to maximize your total score.

Input

The first line contains the number of test cases TT. TT test cases follow in the following format:

The first line of the test case contains NN, the number of cards of each player. A second line follows with NN integers a0,,aN1a_{0},\ldots,a_{N-1}, Mouse Stofl’s card values in the order he’s going to play them. A third line follows with NN integers r0,,rN1r_{0},\ldots,r_{N-1}, the scores of Stofl’s cards. (The ii-th card has value aia_i and score rir_i). A fourth line follows with NN integers b0,,bN1b_{0},\ldots,b_{N-1}, your own card values in an arbitrary order.

Output

For the ii-th test case, output a line “Case #i: M”, where MM is the largest possible total score that you can achieve.

Limits

There are T=100T=100 test cases. In every test case, 1N5000001 \le N \le 500\,000. All scores are 1ri1000001 \le r_i \le 100\,000.

Note that all but at most 1010 test cases in this subtask also satisfy 1N100001 \le N \le 10\,000.

Example

Input:

2
3
2 1 4
4 1 1
0 5 3
3
2 3 5
11 3 7
0 1 4

Output:

Case #0: 5
Case #1: 11

To submit for this subtask, please log in.

Subtask 5 (20 Points)

In this final subtask, all cards have scores. Your total score at the end of the game is the sum of the scores of the cards played by you and by Stofl in the turns that you win. Your goal is still to maximize your total score.

Input

The first line contains the number of test cases TT. TT test cases follow in the following format:

The first line of the test case contains NN, the number of cards of each player. A second line follows with NN integers a0,,aN1a_{0},\ldots,a_{N-1}, Mouse Stofl’s card values in the order he’s going to play them. A third line follows with NN integers r0,,rN1r_{0},\ldots,r_{N-1}, the scores of Stofl’s cards. (The ii-th of Stofl’s cards has value aia_i and score rir_i). A fourth line follows with NN integers b0,,bN1b_{0},\ldots,b_{N-1}, your own card values in an arbitrary order. A fifth line follows with NN integers s0,,sN1s_{0},\ldots,s_{N-1}, the scores of your cards. (The ii-th of your cards has value bib_i and score sis_i).

Output

For the ii-th test case, output a line “Case #i: M”, where MM is the largest possible total score that you can achieve.

Limits

There are T=100T=100 test cases. In every test case, 1N5000001 \le N \le 500\,000. All scores are 1si,ri1000001 \le s_i, r_i \le 100\,000.

Note that all but at most 1010 test cases in this subtask also satisfy 1N100001 \le N \le 10\,000.

Example

Input:

2
3
2 1 4
4 1 1
0 5 3
7 2 3
3
0 3 5
11 3 7
1 2 4
5 2 1

Output:

Case #0: 10
Case #1: 20

To submit for this subtask, please log in.

Don’t hesitate to ask us any question about this task, programming or the website via email (info@soi.ch).

Palatinal Crypt

Below Buda castle in Budapest lies the Palatinal Crypt, a burial place of several Archdukes and Archduchesses from the Habsburg dynasty.

The crypt consists of several rooms that are arranged in an N×MN\times M grid. When the crypt was constructed initially, the rooms were sealed off.

To celebrate the crypt’s 255th birthday, the Hungarian state wants to open up the crypt to the public. For that, some walls should be removed such that all rooms inside the crypt become connected. To preserve the crypt, this should be done by removing strictly less walls than there are rooms.

Furthermore, out of respect to the buried, no room should have all 4 walls removed.

The government has hired Stofl to come up with some plans to satisfy all those constraints. However Stofl can’t find a solution either so he needs your help.

Subtask 1: Klotild Wing (15 points)

The government wants to try out this plan in one of the newer wings of the crypt, the Klotild wing.

Can you help Stofl find a valid solution?

Input

The first line contains a single integer TT, the number of test cases.

TT lines follow, each with two integers NN and MM: There are N×MN \times M rooms.

Output

For the ii-th test case, print a line “Case #i:

This should be followed by an ASCII representation of the crypt with some walls removed. A description of such a representation follows, but it might be easier to look at the examples below.

There should be 2N12\cdot N - 1 lines containing 2M12\cdot M - 1 characters each.
Every second character of every second line, starting with the first character of the first line, should be the letter oo denoting a room of the crypt.
For every pair of rooms that you want to connect (by removing the wall between them), do the following:
  • If the rooms are adjacent horizontally, place a minus sign (“-“) between the corresponding letters oo.
  • If the rooms are adjacent vertically, place a pipe character (“|”) between the corresponding letters oo.
The remainder of the ASCII representation should consist of periods (“.”).
If there are multiple valid ways to satisfy all constraints, you may output any of them.

Limits

  • T=100T=100.
  • 2NM10002 \le N \cdot M \le 1000.

Examples

Input:

2
3 3
4 3

Output:

Case #0:
o.o.o
|.|.|
o-o-o
|...|
o-o.o
Case #1:
o-o-o
..|..
o-o.o
|...|
o-o-o
..|.|
o-o.o

The following is an example of invalid output

Input:

3
3 3
3 3
3 3

Output:

Case #0:
o-o-o
..|..
o-o-o
..|..
o-o-o
Case #1:
o-o-o
|...|
o.o-o
|...|
o-o-o
Case #2:
o-o.o
|...|
o.o.o
..|.|
o-o-o

Comment:

All of those outputs are incorrect. The following paragraphs explain why:

In Case #0, the room in the center of the grid has all four walls removed.

In Case #1, more walls are removed than allowed.

In Case #2, the network is not connected. For example, you can’t get from the top left room to the top right room.

Interactive visualization

To submit for this subtask, please log in.

Feedback

The following example should help you understand some of the automatic feedback you might receive. Click on the box below to see it.

Expand

Input:

3
2 2
2 2
3 4

Output:

Case #0:
o-o
..|
o!o
Case #1:
o-o

..|
o!o
Case #2:
o-o-o-o
....|..
o-o-o-o
....|..
o-o-o-o

Comment:

Feedback for Case #0: “Presentation Error in testcase `Case #0': Invalid character on line 2: Expected `-'/`.' at the position marked with underscores: o_!_o”. Note that line zero is the first line containing output (not including Case #i)

Feedback for Case #1: “Presentation Error in testcase `Case #1': Invalid character on line 2: Expected `-'/`.' at the position marked with underscores: o_!_o”. Note that blank lines are ignored and not counted, which explains why it says line 2 and not line 3.

Feedback for Case #2: “Wrong Answer in testcase `Case #3': You removed 4 walls in the room at position (1, 2), you should have removed one of the following numbers of walls: [0, 1, 2, 3]”. If the grader can understand your ASCII representation but it isn’t a valid answer, it might tell you where the problem lies. The top left room has coordinates (0,0)(0, 0), the next one to the right has coordinates (0,1)(0, 1) etc.

Subtask 2: Ladislaus Wing (10 points)

After further investigation, the government also does not want to have rooms that have exactly 2 walls removed. This demotes the room into a passage which does not pay the proper respect for a burial site.

Stofl does not believe this is possible. Can you show him some examples where this is indeed possible?

Input

The first line of input is TT, the number of crypt layouts you should output. This number is always 20.

This will be followed by TT lines containing the indices of the testcases, i.e. the first line contains the number 00, the second line the number 11 etc.

Note that your program doesn’t actually have to read any input since the input file will always be the same.

Output

Output twenty crypt layouts. For the ii-th crypt, output Case #i: N M with some integers NN and MM of your choice: The height and width of the crypt. After that, output the crypt itself like in Subtask 1. It should have N×MN \times M rooms.

No two crypts may have the same width and the same height. It is, however, allowed to output any number of crypts with the same width or the same height.

Limits

  • T=20T = 20.
  • 2NM10002 \le N \cdot M \le 1000. Note that this isn’t a constraint on the input file, but on your output file.

Example

Input:

2
0
1

Output:

Case #0: 1 2
o-o
Case #1: 2 3
o-o-o
..|..
o-o-o

The following is an example of invalid output

Input:

3
0
1
2

Output:

Case #0: 3 3
o.o.o
|.|.|
o-o-o
|...|
o-o.o
Case #1: 1 2
o-o
Case #2: 1 2
o-o

Comment:

In Case #0, the bottom left room has exactly two walls removed. This is no longer allowed in this subtask, but would have been allowed in Subtask 1.

Case #1 and Case #2 would be OK by themselves, but they use the same width and height.

Interactive visualization

To submit for this subtask, please log in.

Subtask 3: Esztergom Wing (25 points)

Since you’ve convinced Stofl that there are some crypt sizes where the constraints from Subtask 2 can be satisfied, he now wants you to do the same for some other sizes.

Input

Same as Subtask 1.

Output

For the ii-th crypt, print a line “Case #i: Possible” or “Case #i: Impossible”, depending on whether it is possible to remove some walls from a N×MN \times M crypt in order to satisfy all constraints

If it is possible, output the ASCII representation as in Subtasks 1 and 2.

Limits

Same as Subtask 1.

Example

Input:

3
1 2
2 2
2 3

Output:

Case #0: Possible
o-o
Case #1: Impossible
Case #2: Possible
o-o-o
..|..
o-o-o

Interactive visualization

To submit for this subtask, please log in.

Feedback

Note that the automatic grader will not tell you if you wrongly answer “Possible”. It will only point out why your output is not a solution. This can either mean there is a solution, but you did something wrong, or it can mean there is no solution.

Subtask 4 (Theoretical): World Crypt Association (50 points)

Your designs got so much praise that other crypts around the world want to implement a similar scheme. Because Mouse Stofl does not have the time to respond to every request, he wants you to create a well-documented instruction manual so that everybody can figure out which walls to tear down by themselves.

This is a theoretical subtask. Describe an algorithm that can solve subtask 3 and prove its correctness.

Hand in a document (preferably PDF) that describes

  • how your algorithm works. In particular, explain how your algorithm determines whether or not the task is possible and how it constructs a solution if it is possible.
  • why your algorithm is correct. In particular, you should show that the solutions given by your algorithm satisfy all constraints, and that your algorithm only claims the task to be impossible when it actually is.
  • how much time and memory it uses.

Limits

  • NN, MM are variables. You can assume that basic arithmetic operations (addition, subtraction, multiplication, division, and comparison) take a unit time step to perform and that storing one integer uses a single unit of memory.

To submit for this subtask, please log in.

Don’t hesitate to ask us any question about this task, programming or the website via email (info@soi.ch).

Thermal Springs

Hungary is home to a huge variety of thermal water springs, each with different water temperatures, mineral contents or smell. Some springs even come with some nice panorama. Mouse Binna plans to hike around in Hungary and bathe at many different springs. In order for her trip to end on a high note, she wants every spring to be strictly better than the previous: each thermal spring should have a higher water temperature, a higher mineral content, less sulfur smell and more scenery than the previous spring.

Binna has already asked the local wood mice about the various upsides and downsides of each spring. Can you help her plan her trip?

Subtask 1: All the Springs (20 Points)

For her first trip, Binna wants to bathe at all the springs near Szeged, Hungary. Can you help her find a route to do so, or tell her this is not possible?

Input

The first line contains the number of test cases TT. TT test cases follow of the following format:

  • The first line contains one integer NN – the number of springs.
  • The second line contains NN integers tit_i – the temperature of the ii-th spring (0i<N0 \leq i < N).
  • The third line contains NN integers mim_i – the amount of minerals in the water of the ii-th spring (0i<N0 \leq i < N).
  • The fourth line contains NN integers sis_i – the intensity of the sulfur smell at the ii-th spring (0i<N0 \leq i < N).
  • The fifth line contains NN integers pip_i – the beauty of the panorama at the ii-th spring (0i<N0 \leq i < N).

Output

For the tt-th test case print a line “Case #t:” followed by “YES” or “NO”, depending on whether Binna can bathe at all the springs. If the answer was “YES”, then print a single line with NN integers – the order in which Binna can bathe at the springs. (Springs are numbered from 00 to N1N-1.)

Limits

  • T=100T=100.
  • 1N3001 \le N \le 300.
  • 1ti,mi,si,pi1091 \le t_i, m_i, s_i, p_i \le 10^{9}.

Example

Input:

4
2
2 1
2 1
1 2
2 1
2
1 2
1 2
1 2
1 2
3
9 4 7
8 2 3
12 44 13
5 1 4
3
1 1 1
2 2 2
3 3 3
4 4 4

Output:

Case #0: YES
1 0
Case #1: NO
Case #2: YES
1 2 0
Case #3: NO

Comment:

Case #1: If Binna bathes at spring 00 first, the second bath will have too much sulfur smell. If she starts with spring 11, then the second bath (at spring 00) will be too cold.

To submit for this subtask, please log in.

Subtask 2: As Many Springs as Possible (20 Points)

After realizing that she sometimes couldn’t bathe at all the springs, Binna was about to give up on her hike, but then she had an idea: what if she instead tried to bathe at as many springs as possible? Can you help her plan her trip?

Input

Same format as subtask 1.

Output

For the tt-th test case print a line “Case #t:” followed by an integer SS – the maximum number of springs Binna can bathe at while ensuring that every spring is better then the previous. On the next line print SS integers – the springs Binna bathes at, in order. If there are multiple optimal solutions, you may print any one of them.

Limits

  • T=100T=100.
  • 1N3001 \le N \le 300.
  • 1ti,mi,si,pi1091 \le t_i, m_i, s_i, p_i \le 10^{9}.

Example

Input:

4
2
2 1
2 1
1 2
2 1
2
1 2
1 2
1 2
1 2
3
1 1 1
2 2 2
3 3 3
4 4 4
3
4 1 8
2 3 8
9 8 7
1 5 6

Output:

Case #0: 2
1 0
Case #1: 1
0
Case #2: 1
1
Case #3: 2
1 2

Comment:

Note: In cases #1, #2 and #3, there are multiple optional solutions. You may print any of them.

To submit for this subtask, please log in.

Subtask 3: Two Mice (20 Points)

Bathing at this many spring was a lot of fun, but Binna still has nagging thoughts about not having bathed at all the springs. She’s planning another trip to Hungary, but this time, she invited mouse Stofl to come with her. Stofl also likes to bathe and he too wants every spring to be better than the previous one.

The plan is to hike on different routes such that every spring will be bathed at by exactly one mouse. Can you help them plan their trip?

Input

Same as in subtask 1.

Output

For the tt-th test case print a line “Case #t:” followed by “YES” or “NO”, depending on whether Binna and Stofl can find two routes such that every spring will be bathed at by exactly one mouse. If the answer was “YES, then print two more lines. The first line should contain the springs Binna bathes at, it order, and the second line should contain the springs Stofl bathes at, in order. (Springs are numbered from 00 to N1N-1.)

Limits

  • T=100T=100.
  • 1N10001 \le N \le 1000.
  • 1ti,mi,si,pi1091 \le t_i, m_i, s_i, p_i \le 10^{9}.

Example

Input:

4
2
1 2
1 2
1 2
1 2
2
2 1
2 1
1 2
2 1
3
1 1 1
2 2 2
3 3 3
4 4 4
3
4 1 8
2 3 8
9 8 7
1 5 6

Output:

Case #0: YES
1
0
Case #1: YES
1 0

Case #2: NO
Case #3: YES
0 2
1

Comment:

In Case #1, Stofl doesn’t bathe at all.

To submit for this subtask, please log in.

Subtask 4: Big Plans (40 Points)

Together, Binna and Stofl bathed at every thermal spring near Szeged. Now, they have bigger plans: they want to bathe at every single thermal spring in Hungary. Those are a lot of springs, so you better help them find good routes!

Input

Same as in subtask 1.

Output

Same as in subtask 3.

Limits

  • T=100T=100.
  • 1N1000001 \le N \le 100\,000.
  • 1ti,mi,si,pi1091 \le t_i, m_i, s_i, p_i \le 10^{9}.

Note that all but at most 1010 test cases in this subtask also satisfy the limits of the previous subtask.

To submit for this subtask, please log in.

Don’t hesitate to ask us any question about this task, programming or the website via email (info@soi.ch).

Dada

The famous Dada artist Mouse Stofl is making a new artwork right inside the famous “Budavári Labirintus” labyrinth in Budapest. The labyrinth has NN rooms connected with N1N-1 two-way passages in such a way that it is possible to get from any room to any other room. In other words, the rooms and passages form a tree. The rooms are numbered from 00 to N1N-1, and the jj-th passage connects rooms uju_j and vjv_j.

The artwork consists of NN paintings, one in each room. Mouse Stofl has already placed a big white canvas in each of the rooms.

Mouse Stofl has also bought NN buckets of paint of pairwise different colors numbered from 00 to N1N-1 and placed them strategically: the bucket of paint with color ii is in the room ii.

For each of the paintings, Mouse Stofl knows which colors need to be applied to it, but he does not care in particular in which order this will happen. More specifically, the painting in the ii-th room needs kik_i different colors applied: ai,1,ai,2,,ai,kia_{i,1}, a_{i,2}, \dots, a_{i,k_i}, in any order. It is possible that some paintings need to be left untouched (ki=0k_i=0), or that some colors are not needed on any painting.

Mouse Stofl can move between the rooms using the passages either empty-handed or carrying at most one bucket with paint, since those are quite heavy. In order to apply a color to the painting in a room, Stofl needs to bring the corresponding bucket there. Since the buckets are going to be part of the artwork as well, in the end each bucket needs to be brought back to the room where it was in the beginning: the bucket of paint with color ii needs to end up in room ii.

Mouse Stofl does not like to carry heavy buckets around. Can you help him find the minimum number of times he needs to carry a bucket of paint along a passage in order to complete the artwork?

Subtask 1: A single color (10 Points)

In this subtask all paintings either require no paint at all, or require only color 00.

Input

The first line contains the number of test cases TT. TT test cases follow of the following format:

  • The first line contains one integer NN, the number of rooms and colors.
  • The jj-th of the next N1N-1 lines describes the jj-th passage and contains two integers: the numbers uju_j and vjv_j of the rooms this passage connects.
  • The ii-th of the next NN lines describes the painting in the ii-th room: the number kik_i of colors it needs, followed by kik_i distinct colors ai,1,ai,2,,ai,kia_{i,1}, a_{i,2}, \dots, a_{i,k_i}.

Output

For the tt-th test case, output a line containing “Case #t:”, followed by a space and an integer equal to the minimum number of times Stofl needs to carry a bucket of paint along a passage in order to apply all required colors to each painting and then bring each bucket to its original location.

Limits

  • T=100T=100.
  • 2N10002 \le N \le 1000.
  • 0ki10 \le k_i \le 1 for all 0i<N0\le i<N.
  • ai1=0a_{i1} = 0 for all 0i<N0\le i<N such that ki=1k_i = 1.

Example

Input:

1
3
0 1
1 2
1 0
1 0
0

Output:

Case #0: 2

Comment:

Mouse Stofl needs to carry the bucket from room 00 to room 11 and back.

To submit for this subtask, please log in.

Subtask 2: Many colors (15 Points)

In this subtask the paintings may require an arbitrary number of colors.

Input/Output

Same as subtask 1.

Limits

  • T=100T=100.
  • 2N10002 \le N \le 1000.
  • 0kiN0 \le k_i \le N for all 0i<N0\le i<N.
  • The sum ki1000\sum k_i \le 1000.

Example

Input:

1
3
0 1
0 2
0
2 2 1
2 2 0

Output:

Case #0: 6

Comment:

Mouse Stofl needs to carry the bucket with color 00 from room 00 to room 22 and back, and the bucket with color 22 from room 22 through room 00 to room 11 and back.

To submit for this subtask, please log in.

Subtask 3: Apprentices (20 Points)

In this subtask, MM apprentices will be helping Mouse Stofl complete the artwork. Since apprentices are not yet artists, Stofl can only give them a limited type of tasks.

More specifically, for each color ii, Stofl will meet the apprentices in room ii where the bucket with this color is initially placed, and pour some paint of this color into smaller buckets. He will then give some (possibly none or all) apprentices one smaller bucket each, and send them through different passages going from this room. Each apprentice will visit all rooms that they can reach before going back to room ii, and apply the color ii to the paintings in those rooms if necessary. But as soon as an apprentice gets back to room ii, they pour the remaining contents of their small bucket back into the big bucket with color ii, and they do not want to work with this color anymore.

This process is repeated for each color. Note that even though Mouse Stofl can carry the big buckets around, he will not move the bucket with color ii before the apprentices are done with color ii, to avoid confusion. Therefore the apprentices carrying color ii are always sent out from room ii.

Note that if the number of passages connected to room ii is greater than MM, some rooms will not be visited by apprentices carrying color ii, and therefore Stofl might still have to carry the big bucket there himself to apply this color to the painting. In that case he still needs to bring the bucket back to room ii at the end.

For each color ii, Mouse Stofl is free to choose up to MM passages going from room ii that he will send apprentices through in any way. His goal is still to minimize the number of times he needs to carry a bucket through a passage himself.

Input

The first line contains the number of test cases TT. TT test cases follow of the following format:

  • The first line contains two integers NN and MM, the number of rooms and colors, and the number of apprentices.
  • The jj-th of the next N1N-1 lines describes the jj-th passage and contains two integers: the numbers uju_j and vjv_j of the rooms this passage connects
  • The ii-th of the next NN lines describes the painting in the ii-th room: the number kik_i of colors it needs, followed by kik_i distinct colors ai,1,ai,2,,ai,kia_{i,1}, a_{i,2}, \dots, a_{i,k_i}.

Output

For the tt-th test case, output a line containing “Case #t:”, followed by a space and an integer equal to the minimum number of times Stofl needs to carry a bucket of paint himself along a passage in order to apply all required colors to each painting and then bring each bucket to its original location.

Limits

  • T=100T=100.
  • 2N10002 \le N \le 1000.
  • 0M10000 \le M \le 1000.
  • 0kiN0 \le k_i \le N for all 0i<N0\le i<N.
  • The sum ki1000\sum k_i \le 1000.

Example

Input:

1
8 2
0 1
1 2
0 3
4 2
2 5
4 6
5 7
3 7 2 4
0
8 0 1 2 3 4 5 6 7
5 2 3 4 5 6
1 2
8 0 1 2 3 4 5 6 7
8 0 1 2 3 4 5 6 7
1 2

Output:

Case #0: 4

Comment:

For all colors except color 22, the apprentices can do all work. For color 22, Mouse Stofl can send one apprentice toward room 11, and they will also visit rooms 00 and 33 before coming back to room 22. The second apprentice can go toward room 44, and they will also visit room 66. Mouse Stofl will still need to carry the paint himself to rooms 55 and 77.

To submit for this subtask, please log in.

Subtask 4: A Huge Artwork (15 Points)

In this subtask everything is as in subtask 3, but bigger.

Input/Output

Same as subtask 3.

Limits

  • T=100T=100.
  • 2N31052 \le N \le 3 \cdot 10^{5}.
  • 0M31050 \le M \le 3 \cdot 10^{5}.
  • 0kiN0 \le k_i \le N for all 0i<N0\le i<N.
  • The sum ki3105\sum k_i \le 3 \cdot 10^{5}.

Note that all but at most 1010 test cases in this subtask also satisfy the limits of the previous subtask.

To submit for this subtask, please log in.

Subtask 5: Theoretical (40 Points)

You need to analyze how big the answer in this problem can be depending on the values of NN and MM.

More specifically, we define f(N,M)f(N,M) as the maximum possible number of times Mouse Stofl needs to carry a bucket along a passage for any possible input with NN rooms and MM apprentices. You need to provide an upper bound and a lower bound for f(N,M)f(N,M), expressed as formulas with two variables NN and MM, and prove those formulas.

You can consider that N2N \ge 2 and M0M \ge 0, but note that unlike all previous subtasks, there is no upper limit on NN, MM or ki\sum k_i. Your formulas have to cover all possible options for paintings in NN rooms. The proof for the lower bound will typically involve demonstrating an example input achieving this lower bound for each given NN and MM, while the proof for the upper bound needs to consider all possible inputs.

For both bounds, we do not care about a constant factor: for example the formulas f(N,M)2N10f(N,M)\le 2N^{10} and f(N,M)3N10f(N,M)\le 3N^{10}, or any two formulas such that their fraction is bounded by some constant from above and by some positive constant from below, will get the same number of points. In other words you can use the big-O notation for the upper bound and the big-Omega notation for the lower bound. You can read more about those notations in https://soi.ch/wiki/algorithms-intro/.

For example, f(N,M)2N10(M+1)7f(N,M)\le 2N^{10}(M+1)^{7} and f(N,M)1f(N,M)\ge 1 would be a valid answer to this subtask (which you would still need to prove, even if it is not very hard), but it will not give you any points as these are not very tight bounds. f(N,M)=O(N10(M+1)7)f(N,M)=\mathcal{O}(N^{10}(M+1)^{7}) and f(N,M)=Ω(1)f(N,M)=\mathcal\Omega(1) would be another valid way to write this using the big-O and big-Omega notations.

You are free to write down your formulas in any way you like, for example you can also write things like f(N,M)2N10M7f(N,M)\le 2N^{10}M^{7} if M>0M>0, or 2N102N^{10} if M=0M=0.

Grading

Hand in a document (preferably PDF) that contains

  • the upper bound on the number of times Mouse Stofl needs to carry a bucket, as a formula with two variables NN and MM.
  • a proof why the answer will never exceed that value.
  • the lower bound on the number of times Stofl needs to carry a bucket as a formula with two variables NN and MM.
  • a proof why the answer can reach that value (would typically include an example for each pair of NN and MM and an explanation why Mouse Stofl needs to carry a bucket at least this many times in this example).

If your proofs are correct, we will give you the points based on how close are the values computed using your formulas to the real value of f(N,M)f(N,M). The smaller the upper bound is (notwithstanding a constant factor), and the bigger the lower bound is (again notwithstanding a constant factor), the more points you will get.

10 points will be allocated to the lower bound, and 30 points will be allocated to the upper bound.

To submit for this subtask, please log in.

Don’t hesitate to ask us any question about this task, programming or the website via email (info@soi.ch).

Trees

Mouseland got a new subway system thanks to you! One of the subway lines leads out of the city into a newly created nature reserve. Mouse Binna and mouse Stofl were tasked with reforestation of the area to make it more pleasurable for the mice to spend time there.

Unfortunately, Binna and Stofl can’t agree on which type of forest they should plant. While Binna is convinced that the population of Mouseland would prefer oak trees, Stofl thinks they should plant pine trees. As they did not reach a conclusion after hours of discussion, they decided to turn it into a game. Help one of them to win and establish either oak trees or pine trees as the dominant tree in the nature reserve.

Game

The nature reserve is split into multiple points of interest with bidirectional trails between them. Each node ii has some fertility fif_i and some attractiveness aia_i. Initially, there are no trees in the nature reserve.

At the start of the game, the two players are assigned a starting node each. They both plant their type of tree on this node. Once there is some type of tree on a node, the player who is planting this type of tree owns the node. A node will never change the type of tree growing on it once some type of tree grew on it.

Afterwards, the game proceeds in rounds. In each round, a player gets some number of saplings equivalent to the sum of fertility of all the nodes the player owns. Each player can then distribute some or all of its saplings onto empty nodes. Unused saplings can be saved up for future rounds. After the saplings were placed, each node is evaluated in parallel as follows:

  1. The saplings need to be transported from an already owned node but some of them are lost on the way. Specifically, for a certain tree type, let dd be the shortest number of trails which need to be traversed to reach a node where this type already grows. Then, the number of planted saplings is divided by d2d^{2} and rounded down to the nearest integer. This is then the number of saplings actually arriving at this node.
  2. If there are saplings from both types of trees present on the node, the type with more saplings prevails and displaces the saplings of the other type. The displaced saplings are removed from the node. If there is an equal number of saplings from both types on the node, all saplings are removed.
  3. If there still some saplings on the node, this type of tree will now grow on this node and the player planting this type will own the node.

The game ends once all nodes have trees on them or after 2’000 rounds. The player with the higher sum of attractiveness of their nodes wins.

Protocol

The communication between program and server is handled using Stdin / Stdout.

At the start the program receives general information about the game:

One line with nn mm e1e_{1} e2e_{2}, the number of nodes nn, the number of paths mm, your starting node e1e_{1}, and the starting node e2e_{2} of your opponent. On the next line there are nn space separated integers fif_i, the fertility of the ii-th node. On the next line there are nn space separated integers aia_i, the attractiveness of the ii-th node. mm lines follow with two space separated integers bb cc each, denoting a path between node bb and cc.

Now the game starts. For each round you first get two space separated integers u1u_{1} u2u_{2}, the number of saplings u1u_{1} you have available and the number of saplings u2u_{2} your opponent has available in this round. Then you have to print one line with nn space separated integers sis_i, the number of saplings you want to plant on node ii. You will then receive nn lines with two integers tit_i oio_i, the number of saplings tit_i your opponent placed on the ii-th node in this round, and the owner oio_i of the ii-th node: 1-1 for your opponent, 00 for no owner, and 11 if you are the owner.

After the last round you will receive a final line with 1-1 1-1 (i.e. 1-1 for both u1u_{1} and u2u_{2}). Your program should exit.

Limits

These limits apply for all maps and are therefore very general. Take a look at the maps section to get a better idea of the kind of maps you can expect.

  • 3n10003 \le n \le 1000
  • n1mn(n1)n-1 \le m \le n*(n-1)
  • 0e1,e2,b,c<n0 \le e1, e2, b, c < n
  • e1e2e_{1}\neq e_{2}
  • 0fi200 \le f_i \le 20
  • 0ai10000 \le a_i \le 1000
  • 0u1,u2,ti1090 \le u_{1}, u_{2}, t_i \le 10^{9}
  • 1oi1-1 \le o_i \le 1

We aim for n500n \le 500, but due to some randomness in the map generation it is possible that there are a few more nodes.

It is guaranteed that there exists some sequence of trails to get from every node to every other node.

Example

Open the example in the visualization

Attractivity: 0 Fertility: 5Attractivity: 0 Fertility: 3Attractivity: 372 Fertility: 10Attractivity: 584 Fertility: 0Attractivity: 310 Fertility: 3Attractivity: 0 Fertility: 5

The map before the start of the game. Attractivity is displayed in yellow, fertility in green.

Attractivity: 0 Fertility: 5Attractivity: 0 Fertility: 31Attractivity: 372 Fertility: 10Attractivity: 584 Fertility: 01313Attractivity: 310 Fertility: 3Attractivity: 0 Fertility: 5

The moves of the first round. Both have planted the same number on the node in the middle right, so nobody gets it.

Attractivity: 0 Fertility: 5Attractivity: 0 Fertility: 3Attractivity: 372 Fertility: 10Attractivity: 584 Fertility: 0Attractivity: 310 Fertility: 3Attractivity: 0 Fertility: 5

The map after the first round. Red has spent all saplings, blue still has one left.

Attractivity: 0 Fertility: 5Attractivity: 0 Fertility: 3Attractivity: 372 Fertility: 103Attractivity: 584 Fertility: 0313Attractivity: 310 Fertility: 31Attractivity: 0 Fertility: 5

The moves of the second round. Even tough red only put three saplings on the node in the middle right, and blue put 4, red gets the node, because for blue 3 are lost on the way.

Attractivity: 0 Fertility: 5Attractivity: 0 Fertility: 3Attractivity: 372 Fertility: 10Attractivity: 584 Fertility: 0Attractivity: 310 Fertility: 3Attractivity: 0 Fertility: 5

The map at the end of the game. Red has the higher sum of attractiveness, and with that wins the game.

Here is the communication from the point of view of the red player. The input of the program is marked with “<”, and the output with “>”.

< 6 6 0 5
< 5 3 10 0 3 5
< 0 0 372 584 310 0
< 0 1
< 1 2
< 1 3
< 2 3
< 3 4
< 4 5
< 5 5
 > 0 1 0 4 0 0
< 0 1
< 0 1
< 0 0
< 4 0
< 0 0
< 0 -1
< 8 6
 > 0 0 3 3 0 0
< 0 1
< 0 1
< 0 1
< 4 1
< 1 -1
< 0 -1
< -1 -1

Creativity platform

The creativity task will take place on the creativity platform. There you can create new bots, upload the source code for your bots, play games against other participants (or your own bots), view the results of tournaments, and see a ranking of all bots. If you have any questions about the platform do not hesitate to ask us.

A few notes about the platform:

  • The idea is that you create a new bot for a completely new strategy. For small updates to your current strategy just upload a new version for the appropriate bot. There is no hard limit on the number of bots you can create, but we ask you to keep it to a reasonable number.
  • You can not choose the name of your bots. This is to provide some anonymity and we hope that this encourages everyone to play games against each other more freely. If you are unhappy with the name of your bot you can randomize it again as long as you did not yet upload any code.
  • By default, no one can play games against your bots. We think it is very helpful to already play some games before the tournaments and compare your bot with other bots. In order for there to be bots to compare against, some people need to allow others to play games against their bots. So please set your bots to accept games if you feel comfortable doing so. There is also the option where you have to confirm every game so you have better control over which bots you want to play against.
  • If you have bots which require confirmation to play against, don’t forget to check from time to time whether you got any requests.
  • Don’t forget to register your bots for the tournaments. If you abandon a bot please deregister it from the tournaments.
  • The time limit for a bot is 2 minutes per game.
  • If you submit a Java bot, your main class needs to be called BotBot and it may not be in any package.

Subtask 1: Play by the rules (10 Points)

Write a bot that follows the rules and can beat the example bot. Just play and win any game against the random bot on the creativity platform. We have to manually update the scores, so it might take a few days until they show up on the round 1 ranking.

Subtask 2: Play smart (15 Points)

Write a bot which is able to beat our smart bot. Play and win games on at least 5 different map layouts against the smart bot on the creativity platform. You may choose the other map parameters freely. We have to manually update the scores, so it might take a few days until they show up on the round 1 ranking.

Subtask 3: Creativity tournament (75 Points)

You play against other participants of the SOI in multiple tournaments. Based on the rankings of these you will get points.

Each tournament is worth a certain amount of points and you will get a fraction of these based on your rank: 100% for rank 1, then 10% less for every following rank until rank 6 (50%), then 5% less for every following rank. We only include the best bot for each participant in the ranking. However, the creativity platform does not exclude multiple bots from the same person, so the points you receive might not match the displayed ranking.

In the end, your score for this subtask will be the maximal score you achieved during any tournament. There will be the following tournaments:

  • 25.9.2022, 20:00: Early bird tournament, worth 20 points.
  • 9.10.2022, 20:00: Getting started tournament, worth 30 points.
  • 23.10.2022, 20:00: Midway tournament, worth 40 points.
  • 6.11.2022, 20:00: Getting serious tournament, worth 50 points.
  • 20.11.2022, 20:00: Final spurt tournament, worth 60 points.
  • 1.12.2022, 10:00: Creativity tournament, worth 75 points. Ranking will be hidden.

We will update the scores on the round 1 ranking after every tournament, but as we do this manually it might take a few days.

On the creativity platform you can view additional details about the tournaments. A tournament consists of multiple map configurations. For each configuration you will play against every other bot. Each configuration has a score weight sis_i associated with it. For a win on a map you will get 3si3 \cdot s_i, for a draw 1si1 \cdot s_i and for a loss 00 score. The ranking will be according to the sum of these scores across all played games.

Maps

There are a few different map configurations on which we will run the bots. A configuration consists of the following parameters:

  • Map layout: the algorithm to generate the graph.
    • random: Completely random graph
    • line: A line graph
    • star: A generalization of the line map, with a single center and multiple lines originating from there
    • circle: A single circle
    • tree: A random tree (i.e. a connected graph with no circles)
    • treemost: Almost a tree, we start with a random tree and add a few edges
    • wheel: A random graph with high girth (i.e. large cycles)
    • cluster: A treemost graph where each node was replaced by a random graph and each edge by a line
  • Start nodes: whether the two bots start very close or very far from each other.
  • Map fertility: how to select nodes which have fertility.
    • none: No additional fertility on any nodes
    • low/high: Different probabilities for a node having additional fertility
    • all: Every node has additional fertility
    • cluster: Only for cluster map layout, each node in the treemost graph has a 50% probability of having additional fertility in the generated random graph
  • Map attractiveness: how to select nodes which have attractiveness.
    • all1: Every node has 1 attractiveness
    • low/medium/high: Different probabilities for a node having positive attractiveness
    • all: Every node has a random, positive attractiveness
    • cluster: Only for cluster map layout, each node in the treemost graph has a 50% probability of having positive attractiveness in the generated random graph

Hints

It is important for interactive tasks to flush the output buffer after every turn to make sure the server can see your output.

Use the following commands:

  • C/C++: fflush(stdout);
  • C++: cout << flush; (not necessary if you read afterwards)
  • There are similar commands in other languages.

Furthermore it is important that you don’t wait for more characters than the server gives you as an input. For example spaces or line endings in C format strings are a common source for errors. For example if you read the last variable in the input with “scanf("%d ", &x);” it will wait for the next character that is not a space or a line break. You will receive such a character only after you printed your next turn. To solve this use “scanf("%d", &x);” instead (no non-printable characters after the “%d”).

Additional tools

If you want to run your bots locally you can download the judge and the visualization here. This also includes a sample C++ bot. The judge and the visualization both include a short explanation on how to run them. They are the exact same version which is used on the creativity platform, except for some additional sandboxing for the bots.

Don’t hesitate to ask us any question about this task, programming or the website via email (info@soi.ch).

Junior Ranking

RankUsernameTotal (500)paragli… (100)
paragliding
rubiksknob (100)boulders (100)cardgame (100)palatin… (100)
palatinalcrypt
loading ...

Regular Ranking

RankUsernameTotal (600)boulders (100)cardgame (100)palatin… (100)
palatinalcrypt
thermal… (100)
thermalsprings
dada (100)trees (100)
loading ...