Thank you for participating in Kick Start 2019 Round E!

**Cast**

Cherries Mesh: Written by Bartosz Kostka and prepared by Seunghyun Jo and Lalit Kundu.

Code-Eat Switcher: Written by Archie Pusaka and prepared by Reyno Tilikaynen.

Street Checkers: Written by Bartosz Kostka and prepared by Jonathan Irvin Gunawan.

Solutions, other problem preparation, reviews and contest monitoring by Anushi Maheshwari, Himanshu Jaju, Zhang Chen, Sadia Atique, Yang Xiao, Teja Vardhan Reddy Dasannagari.

Analyses were authored by Kevin Tran, Alan Huang and Anushi Maheshwari.

Your friend is recently done with cooking class and now he wants to boast in front of his school friends by making a nice dessert.
He has come up with an amazing dessert called Cherries Mesh. To make the dish, he has already collected cherries numbered 1 to **N**.
He has also decided to connect each distinct and unordered pair of cherries with a sweet strand, made of sugar.
Sweet strands are either red or black, depending on the sugar content in them. Each black strand contains one units of sugar, and each red strand contains two units of sugar.

But it turns out that the dessert is now too sweet, and these days his school friends are dieting and they usually like dishes with less sugar. He is really confused now and comes to your rescue. Can you help him find out which all sweet strands he should remove such that each pair of cherries is connected directly or indirectly via a sugar strand, and the dish has the minimum possible sugar content?

The first line of input gives the number of test cases, **T**.

Each test case begins with a line containing two integers **N** and **M**, the number of cherries and the number of *black* sweet strands, respectively.

Then **M** lines follow, each describing a pair of cherries connected to a black strand. The i-th line contains cherries numbered **C _{i}** and

Note: Any other pair of cherries not present in the input means that they are connected by a red strand.

For each test case, output one line containing `Case #x: y`

, where `x`

is the test case number (starting from 1) and `y`

is minimum possible sugar content.

Time limit: 15 seconds per test set.

Memory limit: 1GB.

1 ≤ **T** ≤ 100

**M** ≤ **N*(N-1)/2**

1 ≤ **C _{i}** ≤

1 ≤

Every {

1 ≤ **N** ≤ 100.

0 ≤ **M** ≤ 100.

For at least 90% of the test cases:

1 ≤ **N** ≤ 1000.

0 ≤ **M** ≤ 1000.

For all test cases:

1 ≤ **N** ≤ 10^{5}.

0 ≤ **M** ≤ 10^{5}.

Sample Input

2 2 1 1 2 3 1 2 3

Sample Output

Case #1: 1 Case #2: 3

n the second sample case, we can keep the black strand between cherry numbered 2 and cherry numbered 3, and remove any of the red strands, which leads to a minimum sugar content of 3.

Umon is a foodie coder. Do you know what two activities that he loves the most? Of course, coding and eating! He always spends the whole day doing only those two activities. However, he thinks that some times of the day are better spent coding, and others are better spent eating.

To illustrate this problem, Umon divides his day into **S** time slots.
During the i-th time slot, if Umon codes 100% of the time, he will achieve **C _{i}** units of coding.
On the other hand, if he eats 100% of the time, he will achieve

Umon needs to plan his schedule for the next **D** days.
On the i-th day, he needs to achieve at least a total amount of **A _{i}** units of coding and

The first line of input gives the number of test cases, **T**.
**T** test cases follow.
Each test case begins with a line containing two integers **D** and **S**, the number of days and the number of time slots in a day, respectively.

Then **S** lines follow, each describing a time slot.
The i-th line contains two integers **C _{i}** and

Then **D** lines follow, each describing a day.
The i-th line contains two integers **A _{i}** and

For each test case, output one line containing `Case #x: y`

, where `x`

is the test case number (starting from 1) and `y`

is a string with **D** characters, where the i-th character is `Y`

if there exists a schedule that can fulfill the target for the i-th day, otherwise it should be `N`

.

Time limit: 20 seconds per test set.

Memory limit: 1GB.

1 ≤ **T** ≤ 100.

1 ≤ **C _{i}** ≤ 10

1 ≤

0 ≤

0 ≤

1 ≤ **S** ≤ 2.

1 ≤ **D** ≤ 10.

For at least TODO% of the test cases:

1 ≤ **S** ≤ 10^{3}.

1 ≤ **D** ≤ 10^{3}.

For all test cases:

1 ≤ **S** ≤ 10^{5}.

1 ≤ **D** ≤ 10^{5}.

Sample Input

2 4 2 3 8 6 10 0 18 3 13 10 0 7 3 1 2 4 4 4 4 0 0

Sample Output

Case #1: YYNY Case #2: Y

In the first sample case, there are 4 days and 2 time slots for each day.

- For day 1, Umon can just eat 100% for both time slots, and therefore achieving a total of 0 units of coding and 8 + 10 = 18 units of eating, thus reaching the target.
- For day 2, Umon can eat 100% of the time for the first time slot, and use 50% of the second time slot for coding and 50% for eating, achieving a total of 0 × 3 + 0.5 × 6 = 3 units of coding, and 1 × 8 + 0.5 × 10 = 13 units of eating, thus reaching the target.
- For day 3, it is impossible to get a total of 10 units of coding.
- For day 4, there are an infinite amount of ways to achieve the target. One possible strategy is to code 42% (and eat 58%) in the first time slot, then code 98.76% (and eat 1.24%) in the second time slot. That strategy yields a total of 0.42 × 3 + 0.9876 × 6 = 7.1856 units of coding, and 0.58 × 8 + 0.0124 × 10 = 4.764 units of eating.

In the second sample case, note that the value of characteristics for the time slots may not necessarily be different from each other.

Alice and Bob are playing a new virtual reality team game - Street Checkers. The game is set on an
insanely long street divided into tiles which are numbered from 0 to 10^{9}(inclusive of both).
At the start of the game, Alice and Bob are standing on tile number 0 and are given a random number X
in range [**L**, **R**] (both ends are inclusive). Alice only jumps to odd numbered tiles,
while Bob only jumps to even numbered tiles. If the number
on the tile divides X, then the player landing on it has to color it with their favorite color.
The game is over after tile X has been colored.

A game is considered interesting by both the players
if the absolute difference between the number of tiles painted by each is not greater than 2. Help
Alice and Bob find how many numbers in the interval [**L**, **R**] could make for an interesting game.

The first line of the input gives the number of test cases, **T**. **T** lines follow
each containing two integers **L** and **R**, the start and end of the interval used to
generate the random number X.

For each test case, output one line containing `Case #x: y`

, where `x`

is
the test case number (starting from 1) and `y`

is the count of numbers in interval
[**L**, **R**] which results in an interesting game for Alice and Bob.

Time limit: 40 seconds per test set.

Memory limit: 1GB.

1 ≤ **T** ≤ 100.

0 ≤ **R** - **L** ≤ 10^{5}.

1 ≤ **L** ≤ **R** ≤ 10^{6}.

1 ≤ **L** ≤ **R** ≤ 10^{9}.

Sample Input

2 5 10 102 102

Sample Output

Case #1: 5 Case #2: 1

For the first sample case, let us look at all the possible number in range [5, 10]:

- 5 - Alice would paint 2 tiles : {1, 5}, and Bob would not paint any tile. The game would be interesting since the absolute difference is 2.
- 6 - Alice would paint 2 tiles : {1, 3}, and Bob would paint 2 tiles : {2, 6}. The game would be interesting since the absolute difference is 0.
- 7 - Alice would paint 2 tiles : {1, 7}, and Bob would not paint any tile. The game would be interesting since the absolute difference is 2.
- 8 - Alice would paint 1 tile : {1}, and Bob would paint 3 tiles : {2, 4, 8}. The game would be interesting since the absolute difference is 2.
- 9 - Alice would paint 2 tiles : {1, 3, 9}, and Bob would not paint any tile. The game would not be interesting since the absolute difference is greater than 2.
- 10 - Alice would paint 2 tiles : {1, 5}, and Bob would paint 2 tiles : {2, 10}. The game would be interesting since the absolute difference is 0.

In the second sample case, we have only one number 102. Alice would paint 4 tiles : {1, 3, 17, 51} while Bob would paint 4 tiles : {2, 6, 34, 102}. The game would be interesting since the absolute difference is 0.

First, let's rephrase the problem: Given a complete undirected graph, where each edge has weight
1 or 2, what is the cost of the Minimum Spanning Tree?
There are a few different algorithms for solving this problem, such as
Prim's Algorithm and
Kruskal's algorithm.
Using Kruskal's Algorithm gives an O(**N**^{2} log **N**) solution per test case,
while Prim's Algorithm gives an O(**N**^{2}) solution per test case.

Intuitively, we want to include as many edges of weight 1 as possible. Once we have included as many such edges as we can, then we know that the remaining edges in the spanning tree will be of weight 2.

Using this idea, we have the following solution: first create a spanning forest using only edges of weight 1. We can now connect each of the components of the spanning forest together using X-1 edges of weight 2, where X is the number of components (we can always connect these components since the graph is complete).

Since we only need to print the minimum cost and not the actual minimum spanning tree, we can simplify the problem to simply counting the number of components in the graph where we only consider the edges of weight 1.

This solves the problem in O(**N**).

Test Data

We recommend that you practice debugging solutions without looking at the test data.

Let's start with the brute force way of solving the problem. We can iterate through all possible coding units for slot 1, let's say X. Now, we can calculate the coding unit left for slot 2 (**A _{i}** -

Let's first solve for only 1 day. So assuming two time slots **S _{i}**(

For calculating minimum coding requirement we can maintain prefix cumulative and
suffix cumulative sum of maximum coding and eating unit that can be achieved in a time slot. Then using binary
search on prefix cumulative sum array, we can find out which minimum indexed time slot will give us eating more than required and we can remove the excess fraction of time for use in coding.
We can compute the maximum coding unit achieved from unused time slots by using the suffix cumulative sum.
This will take O(**SlogS** + **S**) preprocessing time and O(**DlogS**) for each test case.

Test Data

We recommend that you practice debugging solutions without looking at the test data.

Let's rephrase the problem into counting the number of values X within the range [**L**, **R**]
that satisfies |(# of odd divisors) - (# of even divisors)| ≤ 2.

To solve this problem under the constraint that **R** < 10^{6}. We can simply
preprocesses each X between 1 and 10^{6} whether X is
interesting or not. To find whether X is interesting, we can apply any O(√X)
time algorithm finding out all divisors of X. After storing the result for each X, we
build a prefix sum array **F** storing for counts. Thus, each query can be answered by computing
**F**[**R**] - **F**[**L**-1] in constant time.
The total time complexity would then be O(**R _{max}**√

We need a slightly sophisticated observation here. The intuition comes from observing that any
divisor to an odd integer is still odd. For any integer X we can extract all power of 2 factors
and rewrite as X=**A***2^{X}, where **A** is an odd integer and X is a
non-negative integer.

Now, we can partition all divisors to X into sets of divisors leading with each odd divisors
**d _{1}**,

{d,_{1}d*2,_{1}d*2_{1}^{2}, ...,d*2_{1}^{X}},

{d,_{2}d*2,_{2}d*2_{2}^{2}, ...,d*2_{2}^{X}},

...

{d,_{k}d*2,_{k}d*2_{k}^{2}, ...,d*2_{k}^{X}}.

By looking at the above diagram we can infer that X has X odd divisors and X*X even divisors. The criteria to a number being interesting is now equivalent to |X*(X-1)| ≤ 2.

There are only a few cases of (X, X) pairs that satisfies the above expression:

- Case 1: X=0, X=1 or 2.
- Case 2: X=1, X can be any value.
- Case 3: X=2, X=1 or 2.
- Case 4: X=3, X=1.

So, what we really need to do here is to count the number of X's in the range [**L**, **R**]
satisfying each case.

Case 1 implies that X=1 or a odd prime. One can count the number of primes within range
[**L**, **R**] using Sieve
of Eratosthenes.
Case 2 implies that **A** can be any odd integer, so in this case X is in the form of
(4*X+2) and hence can be counted in O(1) time.
Case 3 implies that **A**=1 or an odd prime. One can count the number of primes within range
[**L**/4, **R**/4].
Case 4 implies that X=8. Count it whenever 8 belongs to the range.

From the above case analysis, one can see that the running time is dominated by
Sieve of Eratosthenes. Fortunately, we only need to use sieve method on arrays of size
O(**R**-**L**+1) to count the number of odd primes within ranges [**L**, **R**] and
[**L**/4, **R**/4]. If we apply sieving using numbers 2, 3, 4, ..., √**R**, the
algorithm runs in O(**T***(**R** - **L** + 1)*log(√**R**)) time,
which suffices to pass this test set.

For a more efficient algorithm, one can sieve using prime numbers no more than √**R**.
These prime numbers again can be
obtained by a sieving algorithm. At the end you will get an algorithm that runs in
O(√**R** log log √**R**) + O((**R** - **L** + 1) log log √**R**) time
per test case.

Test Data

We recommend that you practice debugging solutions without looking at the test data.