It is an interesting problem in graph theory called “graph coloring”.

In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called “colors” to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices share the same color; this is called a vertex coloring. (from Wikipedia)

The smallest number of colors needed to color a graph is called its chromatic number.

the student asks: I wonder if this problem is easy on trees.

the teacher explains: Well, two colors is enough for trees.

But the critical thinking student thought he should better check that. He thought it is too simple to be true.

Note: the tree is a connected graph with no cycles.

John is a successful farmer and he would like to expand his business. For this reason he is going to buy a new plot of land to grow even more crops (and earn even more money). Currently there are T (0 ≤ T ≤ 1000) plots on sale and John wants to find the best deal. He considers deal the best if the price per area unit is the lowest. Can you help him by coding a solution that computes price per area unit?

Jonas is reading the book called “Algorithms and Data Structures (for extremely experienced computer scientists edition)”. He learned a new data structure - the array of lowercase letters. As Jonas is innovative and you are his good friend, he assigned you the task to implement and to use the array of uppercase letters. This data structure is mainly a string with only uppercase letters which can operate two types of queries:

• “s l r” - sorts letters in the interval [l;r] (0 ≤ l ≤ r <  length of string);
• “g l r” - prints frequences of all letters from A to Z in the interval [l;r].

The lightning usually hits towers, tall buildings. Have you noticed that? The thing is that they are near the“source of power”.

We will use this lightning model (which may be not true in real world). Every direct path in which the lightning can strike is characterized by its non-resistance (the bigger non-resistence, the bigger power of the lightning) and its length.

There are n objects (k of them are the targets at which the lightning can strike). We say the path has power x if the minimum non-resistence along the path is x.

The lightning could be modelled as follows:

1. The maximum power P the lightning can strike is calculated. It is the minimum non-resistence of a path with the biggest power from the source of power to the one of the k targets.
2. Then the minimum distance is calculated which has the path with power P from the source of power to the one of the k targets. It's guaranteed that it will be possible to find at least one such path.
3. All targets which have the path with minimum found distance with power P are called dangerous (because they are open for the strike).

Do you know how magicians cast spells? The spell consists of its name and its magical code. The casting is done by saying its name while keeping in mind the magical code (only then the spell works). Only the most experienced, the smartest and the most talented magicians can create they own spells. They name their spell and determine its purpose. They make some rituals near the Tree of Power. And if the magician is worth the tree creates the magical code for this spell.

However, the tree itself is designed and created by the mathematician who told me the mechanism of creating spells. Here is the algorithm in “our language”:

const int MOD = 1013;

int code = 0;

for (int i = 0; i < spell_name.size(); i++)

    code = (code * 31 + spell_name[i]) % MOD;

printf("You are worth it! Your power is unleashed by the number %d" , code);

The creator of the tree wants to boost your knowledge. So he tells some of the most recent codes and parts of the spell’s name. You need to tell what the maximum number of spells could have this magical code. If there is only one choice - print it!

Note: the spell’s name consists only of lowercase English alphabet letters (’a’-’z’).

Two powerful magicians “The king of fire” and “The hero of ice” are fighting each other to conquer the world. The winner will be the one who is the smarter and…a bit more successful.

The fight between two greatest magicians involves a lot of strategy because magicians can cast only limited amount of spells during each moment of time.

You support the king of fire just because the summer has just ended and you want to swim in the sea and to play volleyball in the beach… Ah, these good summer days! It may be possible again with the power of fire!

Each magician is characterized by hp (health points), atk (the strength of the attack), def (the defence abilities). Each spell is one of the following types:

• “Heal x”, which changes hp to min(current_hp + x;10);
• “Atk x”, which changes atk to max(current_atk;x);
• “Def x”, which changes def to max(current_def;x);
• “HIT!”, which deals damage to the opponent which equals max(0;attacking_atk - defending_def);

Opponent loses the dealt damage points from his hp. If player’s hp becomes less than or equal to 0 he is considered dead and his opponent is a winner.

Each player starts with hp = 10, atk = 0, def = 0. Luckily the king of fire moves first. It may increase our chances!

Each player has a sequence of 10 spells. He can reuse the same spell again. During the first turn a magician can use the first 5 spells, during the second - the first 6 spells and so on…During the turn a magician can cast only one spell.

Note: assume that both magicians are very wise and don’t make mistakes, i.e. they play optimally well. It means that a magician tries to minimize the number of turns if it is possible to win. If it is impossible to win, then a magician tries to maximize the number of turns.

Note: it is guaranteed that the winner exists and the game ends in at most 12 turns (that’s it, at most 6 turns for one player).

The pair in the land of 1000000007 is the pair of numbers a and b with the following relation: a × b = 1 (mod 1000000007). It is believed to be the sign of divine. Your task is to increase the number of happy marriages so you must find the maximum number of distinct pairs! Distinct pairs can not have the same number (with the same index). Pairs are different when the sets of their indices are different

People like magic. Magic is powerful, interesting and mysterious. However, the real magicians are not more than talented cheaters. One of the most famous magicians is David Foolfield.

For example, suppose there is a room with a tied magician. Then the doors are closed, opened again - there is no magician and he appears in some other room. The thing we don’t know that there are secret doors that connect rooms with each other. Of course, he may use another cheap trick - to hide in the same room and his assistant that looks the same appears in the other room. However, we assume that there are no assistants in this problem.

We finally figured out the secret paths between the rooms. Now we want to calculate in how many rooms (other than the initial) the magician can appear. The magician can appear in any room which can be reached from the starting room directly or indirectly.

You have a simple system in which you want to have a search function. You decided to implement it for searching email addresses. There is a bunch of email addresses in your program.

User enters an email address. And the function detects if there is one. If yes, then its answer is “yes”, otherwise it tries to change one symbol in the entered address (the error detection). Then, if it matches only one address, the answer is still “yes”. But if it detects more than one address or does not detect anything, the answer is “no“.

Tom has just found out that he can’t make a triangle using three line segments of lengths 1, 2 and 5. He has lots of different line segments and wants to know how many different triangles he can make. The triangles are different if the sets of their line segments’ lengths are different.