Przykładowe zadania 

Problem A - Party

Suppose w have a party of n people. We know if any of two of them are acquainted with each other. We would like to know more about triples of people that are mutual acquaintances.

Please calculate:
t - the number of different triples of people that are mutual acquaintances
m - the maximum number of triples that a person belongs to, and
k - the number of persons that belong to exactly m triples


Input
The first line of the input contains n - the number of persons. In the line that follow there are pairs of numbers i,j denoting that two people with these numbers on the list of participants are acquainted with each other. The end of the input is marked by the pair 0 0.

Output
The ouput consists of three numbers: t, m and k.

EXAMPLE

Input
 
8
1 2  2 3  2 5  2 6  2 7  2 8  3 4  3 5  3 6  3 7
3 8  5 6  6 8  7 8
0 0
Output
 
t = 10
m =  7
k =  2


Problem B -Squares

B. Kordiemski in his book on mathematical puzzles has included the following task:
Let's consider a square of size N x N (N<=100). The square is filled with all the integer numbers from 1 to N*N located in it randomly. Each position is described by its coordinates [r, c] where r describes the row number and c is the column number (r, c >=1). See the following figure: 
4 6 9
3 8 2   (Fig. 1)
7 1 5
You have to place the numbers in the ascending order - the final square should be as follows:
 
1 2 3
4 5 6   (Fig. 2)
7 8 9
In order to obtain such a result you can swap 2 positions in a square. For instance you can swap positions [3, 2] and [1, 1] in Fig. 1. After that you will obtain the following square:
 
1 6 9
3 8 2   (Fig. 3)
7 4 5
Then you can swap another pair of positions. Each swapping is a single move. Your goal is to determine the minimal number of moves necessary to obtain the ascending order of numbers for a given square. To avoid the unnecessary moves you should try to invent a kind of swapping strategy (which pairs should be swapped in what order).

Input
The input contains:
  • N - the number of rows equal to the number of columns
  • a square - sequence of integer numbers constitutioning the square
Output
The ouput should contain the minimal number of moves necessary to obtain the ascending order in a given square.

Suggestion
Let's consider the following square:
 
3 2 5
4 7 8   (Fig. 4)
1 9 6
In that case, if you want to obtain the minimal number of swappings, you have to move number 1 from position [3, 1] to [1, 1], number 7 from [2, 2], to [3, 1], number 5 from [1, 3], to [2, 2] and number 3 from [1, 1], to [1, 3]. You can do it by the following swappings:

swap [3, 1] and [1, 1]
swap [3, 1] and [2, 2]
swap [2, 2] and [1, 3]

Another group of swappings is connected with numbers 6, 8 and 9. You have to move number 6 from [3, 3] to [2, 3], number 8 from [2, 3] to [3, 2] and number 9 from [3, 2] to [3, 3]. You can do it by swappings:

swap [2, 3] and [3, 3]
swap [3, 2] and [3, 3]

(Note that, the numbers 2 and 4 remain untouched as they are at the right positions in the input square).

Making the above 5 swappings gives you (as a result) the ordered square and this is also the minimal number of swappings necessary to get such a square.

EXAMPLE

Input
 
3
3 1 5
4 2 8
6 7 9
Output
 
Movements: 5
EXAMPLE 2

Input
 
4
16 15 14 12
12 11 10  9
 8  7  6  5
 4  3  2  1
Output
 
Movements: 8


Problem C - Minimal pour out of vessels

We can use a set of vessels to fill a tank with a precisely stated amount of fluid. The problem is to use them in an optimal way to avoid too much labour and inadequacy. For simplicity we assume that we have a tank of capacity more than 10000 liters and a set of vessels with precise capcity in liters. We can use vessels to fill the tank (using tap to fill a vessel first), and we can also use vessels to empty it (using sink to empty the vessel next). We should minimize the number of the fill and pour away operations of the tank to obtain the given amount of fluid inside.

Your program has to read the capacity of each vessel (we will have no more than 1000 vessels) and the amount of fluid the tank should be filled with.

The program should compute number of the fills and pours away to obtain a given amount of fluid inside in an efficient manner.

Suggestion
Algorithm of exponential-time complexity will probably not be accepted, because it can exceed the execution time limit.

Input
  • the input contains as many lines as problems to solve, plus one line with a single 0 (zero) to denote the end
  • each problem line is a sequance of positive lintegers each not greater than 5000, describing the amount of fluid the tank should be filled with and the capacities of available vessels; 0 (zero) denotes the end of the line.

Output
a separate line for each, set of vessels containing the minimal number of add and pour away operations or the string "Impossible" in the case the solution does not exist.

EXAMPLE

Input
 
8 3 7 0
5 3 7 0
5000 2 4 12 11 34 0
17 2 4 8 0
0
Output
 
4
5
148
Impossible