## Задача A. Breadth First Search ≡

• задачи
 Автор: StdAlg Ограничение времени: 1 сек Входной файл: input.txt Ограничение памяти: 256 Мб Выходной файл: output.txt

### Условие

Требуется написать программу, которая получает невзвешенный неориентированный граф и выводит все его вершины в порядке увеличения расстояния от данной вершины S. Расстояние между вершинами A и B это длина кратчайшего пути из A в B. Если есть несколько вершин, находящихся на одном и том же расстоянии от вершины S, выведите их в произвольном порядке.

### Формат входного файла

Входной файл содержит три целых числа N, M и S, где M — число рёбер, S — номер стартовой вершины. Вершины пронумерованы целыми числами от 1 до N. Каждая из следующих M строк содержит пару целых чисел — номера вершин, соединённых ребром.

### Формат выходного файла

Выходной файл должен содержать последовательность из N номеров вершин, упорядоченных по возрастанию расстояния от S. Если какая-то из вершин недостижима из S, выведите единственное число  − 1.

### Ограничения

0 ≤ N, M ≤ 100000

### Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
3 2 1
1 2
2 3
1 2 3

## Problem B. Topological sorting ≡

 Author: StdAlg Time limit: 1 sec Input file: input.txt Memory limit: 8 Mb Output file: output.txt

### Statement

You are to write a program that performs a topological sorting of a directed graph. Graph contains N vertices, numbered with integers from 1 to N, and M edges.

In other words, given a partial order on numbers from 1 to N, your program must produce some linear order on these numbers which does not conflict with the given partial order.

### Input file format

Input file contains two integers N and M, followed by M pairs of integers. Integers in each pair are different, and represent starting and ending vertex of a graph edge.

These pairs may also be considered comparisons where the first number precedes the second one.

### Output file format

Output file must contain a permutation of integers from 1 to N — numbers of vertices sorted in topological order. (That is, representing a linear order.) If ordering is not possible, output file must contain a single number  − 1.

### Constraints

0 ≤ N, M ≤ 100000

### Sample tests

No. Input file (input.txt) Output file (output.txt)
1
4 3
1 2
1 3
3 4
1 3 2 4

## Problem C. Biconnectivity ≡

 Author: StdAlg Time limit: 1 sec Input file: input.txt Memory limit: 64 Mb Output file: output.txt

### Statement

You are to write a program that receives a connected undirected graph and finds all its articulation points, which are the vertices that, if removed, leave disconnected graph.

### Input file format

Input file contains two integers N and M. Vertices are numbered with integer numbers from 1 to N. M is the number of edges. Each of next M lines contain pair of integers — numbers of vertices connected by an edge. There are no pairs of equal numbers.

### Output file format

Output file must contain integer representing a quantity of articulation points, followed by numbers of corresponding vertices in arbitrary order.

### Constraints

1 ≤ N, M ≤ 100000

### Sample tests

No. Input file (input.txt) Output file (output.txt)
1
5 6
1 2
1 3
2 3
1 4
1 5
4 5
1 1

## Problem D. Dijkstra ≡

 Author: StdAlg Time limit: 1 sec Input file: input.txt Memory limit: 16 Mb Output file: output.txt

### Statement

You are to write a program that receives a weighted directed graph and finds distances from source vertex S to all other vertices. Distance from S to some vertex W is the minimal length of path going from S to W. Length of path is the sum of weights of its edges.

Vertices are numbered with integers from 1 to N.

### Input file format

First line of input file contains three integers N M and S, where M is the number of edges. Next M lines contain three integers each — starting vertex number, ending vertex number and weight of some edge respectively. All weights are positive. There is at most one edge connecting two vertices in every direction.

### Output file format

Output file must contain N integers — distances from source vertex to all vertices. If some vertices are not reachable from S, corresponding numbers must be −1.

### Constraints

1 ≤ N ≤ 1000. All weights are less or equal than 1000.

### Sample tests

No. Input file (input.txt) Output file (output.txt)
1
5 3 1
1 2 5
1 3 7
3 4 10
0 5 7 17 -1

## Problem E. Fast Dijkstra ≡

 Author: StdAlg Time limit: 1 sec Input file: input.txt Memory limit: 8 Mb Output file: output.txt

### Statement

You are to write a program that receives a weighted directed graph and finds all distances from fixed vertex S to all other vertices. Distance from S to some vertex W is the minimal length of path going from S to W. Length of path is the sum of weights of its arcs.

### Input file format

Input file contains two integers N, M and S. Vertices are numbered with integer numbers from 1 to N. S is the number of source vertex. M is the number of arcs. Each of next M lines contain three integers — numbers of starting and ending vertices of some arc and its weight respectively. All weights are positive. There is at most one arc connecting two vertices in every direction.

### Output file format

Output file must contain N numbers. Each I-th number is the distance from vertex S to vertex I. If some vertices are not reachable from S, corresponding numbers must be −1.

### Constraints

1 ≤ N, M ≤ 100000 All weights are less or equal 1000.

### Sample tests

No. Input file (input.txt) Output file (output.txt)
1
5 3 1
1 2 5
1 3 7
3 4 10
0 5 7 17 -1

## Problem F. Shortest Spanning Tree ≡

 Author: StdAlg Time limit: 1 sec Input file: input.txt Memory limit: 16 Mb Output file: output.txt

### Statement

You are to write a program that receives a weighted undirected graph and finds length of its shortest spanning tree.

### Input file format

Input file contains two integers N, M. Vertices are numbered with integer numbers from 1 to N. M is the number of edges. Each of next M lines contain three integers describing an edge — numbers of vertices, connected by an edge and its weight respectively. All weights are positive. There is at most one edge connecting two vertices.

### Output file format

Output file must contain a signle integer number — length of the SST. If it is impossible to construct spanning tree, output file must contain −1.

### Constraints

1 ≤ N ≤ 1000 All weights are less or equal 1000.

### Sample tests

No. Input file (input.txt) Output file (output.txt)
1
3 3
1 2 10
2 3 10
3 1 10
20

## Problem G. SST for sparse graph ≡

 Author: StdAlg Time limit: 1 sec Input file: input.txt Memory limit: 8 Mb Output file: output.txt

### Statement

You are to write a program that receives a weighted undirected graph and finds length of its shortest spanning tree.

### Input file format

Input file contains two integers N, M. Vertices are numbered with integer numbers from 1 to N. M is the number of edges. Each of next M lines contain three integers describing an edge — numbers of vertices, connected by an edge and its weight respectively. All weights are positive. There is at most one edge connecting two vertices.

### Output file format

Output file must contain a signle integer number — length of the SST. If it is impossible to construct spanning tree, output file must contain −1.

### Constraints

1 ≤ N, M ≤ 100000 All weights are less or equal 1000.

### Sample tests

No. Input file (input.txt) Output file (output.txt)
1
3 3
1 2 10
2 3 10
3 1 10
20

## Problem H. Eulerian cycle ≡

 Author: StdAlg Time limit: 1 sec Input file: input.txt Memory limit: 64 Mb Output file: output.txt

### Statement

You are to write a program that receives an undirected connected graph and finds its Eulerian cycle.

### Input file format

Input file contains two integers N, M. Vertices are numbered with integer numbers from 1 to N. M is the number of edges. Each of following M lines contains a pair of vertex numbers, connected by some edge. There is at most one edge connecting two vertices.

### Output file format

Output file must contain a sequence of vertex numbers in order of traversal in an Eiler cycle. If there does not exist any Eiler cycle, output file must contain  − 1.

### Constraints

1 ≤ N, M ≤ 100000

### Sample tests

No. Input file (input.txt) Output file (output.txt)
1
3 3
1 2
2 3
3 1
1 2 3 1

## Problem I. Floyd-Warshall ≡

 Author: StdAlg Time limit: 1 sec Input file: input.txt Memory limit: 8 Mb Output file: output.txt

### Statement

You are to write a program that finds shortest distances between all pairs of vertices in a directed weighted graph. Graph consists of N vertices, numbered from 1 to N, and M edges.

### Input file format

Input file contains two integers N and M, followed my M triplets of integers ui vi wi — starting vertex, ending vertex and weight or the edge. There is at most one edge connecting two vertices in every direction. There are no cycles of negative weight.

### Output file format

Output file must contain a matrix of size NxN. Element in the j-th column of i-th row mush be the shortest distance between vertices i and j. The distance from the vertex to itself is considered to be 0. If some vertex is not reachable from some other, there must be empty space in corresponding cell of matrix.

### Constraints

0 ≤ N ≤ 100. All weights are less than 1000 by absolute value.

### Sample tests

No. Input file (input.txt) Output file (output.txt)
1
3 3
1 2 5
1 3 10
2 3 2
0 5 7
0 2
0

## Problem J. Ford-Bellman ≡

 Author: StdAlg Time limit: 1 sec Input file: input.txt Memory limit: 8 Mb Output file: output.txt

### Statement

You are to write a program that finds shortest distances from vertex S to all other vertices in a given directed weighted graph. Graph consists of N vertices, numbered from 1 to N, and M edges.

### Input file format

Input file contains two integers N M S, followed my M triplets of integers ui vi wi — starting vertex, ending vertex and weight or the edge. There is at most one edge connecting any two vertices in every direction. There are no cycles of negative weight.

### Output file format

Output file must contain a vector of N integers — distances from vertex S to other vertices. The distance from any vertex to itself is considered to be 0. If some vertex is not reachable from S, corresponding cell of the vector must contain empty space.

### Constraints

0 ≤ N, M ≤ 1000. All weights are less than 1000 by absolute value.

### Sample tests

No. Input file (input.txt) Output file (output.txt)
1
3 3 1
1 2 5
1 3 10
2 3 2
0 5 7

## Problem K. Strong connectivity ≡

 Author: StdAlg Time limit: 1 sec Input file: input.txt Memory limit: 8 Mb Output file: output.txt

### Statement

You are to write a program that receives a directed unweighted graph and finds all vertices of its strong-connected component, containing given vertex S.

### Input file format

Input file contains two integers N, M and S. Vertices are numbered with integer numbers from 1 to N. M is the number of arcs. Each of next M lines contain pair of integers — starting and ending vertices of some arc respectively. There is at most one arc connecting two vertices in every direction.

### Output file format

Output file must contain integer number T — amount of vertices in strong-connected component. After that, there must be T integer numbers in ascending order — vertices of compontent themselves.

### Constraints

0 ≤ N, M ≤ 100000.

### Sample tests

No. Input file (input.txt) Output file (output.txt)
1
5 4 1
1 2
2 3
3 1
4 1
3 1 2 3

## Problem L. Square sort ≡

 Author: StdAlg Time limit: 1 sec Input file: input.txt Memory limit: 8 Mb Output file: output.txt

### Statement

You are to write a program that receives a sequence of integer numbers and sorts it, i. e. writes out all elements in ascending order.

### Input file format

Input file contains integer N — length of the sequnece, followed by N integer numbers — elements of the sequence.

### Output file format

Output file must contain N integer numbers, which must be elements of the source sequence printed in ascending order.

### Constraints

0 ≤ N ≤ 3000. Sequence elements are less than 109 by absolute value.

### Sample tests

No. Input file (input.txt) Output file (output.txt)
1
5 4 3 10 3 1
1 3 3 4 10

## Problem M. Lin-log sort ≡

 Author: StdAlg Time limit: 1 sec Input file: input.txt Memory limit: 8 Mb Output file: output.txt

### Statement

You are to write a program that receives a sequence of integer numbers and sorts it, i. e. writes out all elements in ascending order.

### Input file format

Input file contains integer N — length of the sequnece, followed by N integer numbers — elements of the sequence.

### Output file format

Output file must contain N integer numbers, which must be elements of the source sequence printed in ascending order.

### Constraints

0 ≤ N ≤ 100000. Sequence elements are less than 109 by absolute value.

### Sample tests

No. Input file (input.txt) Output file (output.txt)
1
5 4 3 10 3 1
1 3 3 4 10

## Problem N. Knuth-Morris-Pratt ≡

 Author: StdAlg Time limit: 1 sec Input file: input.txt Memory limit: 256 Mb Output file: output.txt

### Statement

You are to write a program that receives two strings and finds position where the second string appears in the first one as a substring.

### Input file format

First and second lines of input file contain given strings. Each string is a sequence of lower-case Latin letters from 'a' to 'z' and spaces.

### Output file format

Output file must contain a single integer — position of the first occurrence of the substring in a string, or  − 1 if there is none. Positions are numbered from 1.

### Constraints

Length of each string does not exceed 100000 characters.

### Sample tests

No. Input file (input.txt) Output file (output.txt)
1
yezhiki nachinayut i vyygryvayut
yut
16

## Problem O. Bucket sort ≡

 Author: StdAlg Time limit: 3 sec Input file: input.txt Memory limit: 16 Mb Output file: output.txt

### Statement

You are to write a program that receives a sequence of words and sorts it in lexicographical order. Linear order on characters is given by ASCII codes.

### Input file format

First line of input file contains integer N — the sequence length. Following N lines contain one word per line. Each word is exactly three letters long.

### Output file format

Output file must consist of N lines, each containing one word from sorted sequence.

0 ≤ N ≤ 1000000.

### Sample tests

No. Input file (input.txt) Output file (output.txt)
1
4
KVN
ACM
FSB
GGG
ACM
FSB
GGG
KVN

## Problem P. Binary Witch ≡

 Author: Far-Eastern Subregional Time limit: 3 sec Input file: input.txt Memory limit: 32 Mb Output file: output.txt

### Statement

Once upon a time in the silent depths of digital forests there lived a Binary Witch. She was able to forecast weather, telling for any day in the future whether it will be rainy or sunny.

Her magic was based on the following ancient rule: let a1, a2, ..., aN be the sequence of binary digits, where ai=0 indicates that i-th day was rainy, and ai=1 - that it was sunny. To predict the weather in day N + 1, consider the t-postfix aN-t+1, aN-t+2, ..., aN consisting of the last t elements. If that postfix is encountered some- where before the position N - t + 1, i.e. if there is such k ≤ N - t, that ak = aN-t+1, ak+1 = aN-t+2, ..., ak+t-1 = aN then the predicted value will be ak+t. If there is more than one occurrence of t-postfix, then the rightmost one (with maximal k) will be taken. So, to make a prediction, she tried t-postfixes, consequently for t = 13, 12, ..., 1, stopping after the first prediction. If neither postfix was found, she predicted rain ("0"). If prediction for more than one day is needed, it is assumed that all previous days are predicted correctly, so if first predicted value is b, then we make forecast for day N + 2 based on N + 1 values, where aN+1 = b.

Because the witch was burned long ago, your task is to write a program to per- form her arcane job.

### Input file format

First line of input file contains two integers N and L, separated by space. Second line contains a string of N characters "0" and " 1".

### Output file format

Output file must contain a single string of L characters, which are forecasts for days N+1, N+2, ..., N+L.

### Constraints

1 ≤ N ≤ 100000 1 ≤ L ≤ 1000

### Sample tests

No. Input file (input.txt) Output file (output.txt)
1
10 7
1101110010

0100100

## Problem Q. Fool Game ≡

 Author: Far-Eastern Subregional Time limit: 3 sec Input file: input.txt Memory limit: 8 Mb Output file: output.txt

### Statement

The game of fool is played with a small set of cards, which includes nine ranks - 6, 7, 8, 9, 0 (10), J (Jack), Q (Queen), K (King), A (Ace) of the four suits each - h (Hearts), s (Spades), d (Diamonds) and c (Crosses). So, for example a queen of spades is denoted Qs, and a ten of diamonds is 0d. One of the suits is declared a trump. During the game, the card beats another card, if either it has the same suit and higher rank, or it is a trump, while the beaten card is not.

In the game, a move proceeds as following. First player puts one of his cards on the desk, and the second player can either beat it with one of his cards, putting his card over it, or take it, if he has no suitable card. If the card is beaten, first player may flip in any of his remaining cards, which has same rank as any card already on the desk. This card, in turn, may be beaten or taken together with all other cards on the desk, etc. For example, if first player has cards 6s6dQhKd, the second player has 6h7h0sQd and hearts are the trumps, then first player can move with Kd, which is beaten with 6h, then flip in 6s, beaten by 0s, then 6d, beaten by Qd and at last Qh, which can not be beaten with 7h, so the second player has to take it.

Your task is to write a program that, given the trump suit and first and second playerTs cards, determines for the first player such a move as to eventually make the second player take.

Your task is to write a program that, given the trump suit and first and second playerTs cards, determines for the first player such a move as to eventually make the second player take.

If there is more than one such move, the program must find one with smallest rank. If there is several moves with smallest rank, program must choose the card with the first suit in the order mentioned in the first paragraph (i.e. h < s < d < c). In the example above, second player could beat Kd with 7h, thus preventing further flips. On the other hand, move of Qh will be immediately taken.

### Input file format

In the first line of input file there is a single character h, s, d, or c, determining a trump suit. On the second line there is a string denoting first playerTs cards, and on the third line S the string with the second playerTs cards. All cards are different, and the players have equal number of cards.

### Output file format

Output file must contain a single line with either a card to move or a string "NO", if a program was unable to find it.

### Sample tests

No. Input file (input.txt) Output file (output.txt)
1
s
As7h8dJc
Jd8s7c0c

7h

 Author: Far-Eastern Subregional Time limit: 3 sec Input file: input.txt Memory limit: 8 Mb Output file: output.txt

### Statement

You are to write a program emulating a very simple spreadsheet application. It works with a table with 9 rows, from "1" to "9", and 26 columns, from "A" to "Z". Table cells are referenced by names composed of column and row codes, ex. "B1", "S8".

Each cell contains an expression up to 255 characters long. Expressions use integer constants, cell references, parenthesis, operators "+", "-", "*", and "/" (whole division). For example: 567, E8/2, (3+B3)*(C4O1) are all valid expressions. All opera- tors are whole, all arguments and results are guaranteed to be less than 1000000. Divi- sion by zero yields zero.

If the value of the cell referenced by some expression is not defined, it is pre- sumed to be 0 (zero). The situation when two or more cells are mutually dependent on each other is considered a special case of circular reference.

### Input file format

First input line contains number of expressions N. Following N lines are in format <Cell reference>=<expression>. All expressions are correct, and each cell is defined by at most one expression.

### Output file format

Output file must contain single line with either the value of the cell "A1" or number 1000000 (one million) if the value of A1 cannot be computed due to a circular reference.

### Sample tests

No. Input file (input.txt) Output file (output.txt)
1
4
A1=B1+C5
B1=20
C5 =B1 /D7-E1*E1
E1=(3+1)*2

-44

## Problem S. PreQueL ≡

 Author: Far-Eastern Subregional Time limit: 3 sec Input file: input.txt Memory limit: 8 Mb Output file: output.txt

### Statement

In some simplistic DBMS named PreQueL, the only column type allowed is CHAR(1) (a single character), and furthermore, its values are restricted to English upper- case letters (eAi to eZi). Table may contain up to 9 columns, numbered from 1 to 9. Tables themselves are named with lower-case English letters (eai to ezi).

The only database query possible first joins all the tables, then selects some rows according to conditions in one of two forms: either <column>=<value> or <column1>=<column2>, for example a2=A or b1=c4. All conditions must hold simultaneously, as if they were connected by eANDi operator.

You must write a PreQueL processor, which, given a tables and a set of conditions, will produce query result, i.e. those rows of a join satisfying all the conditions. Resulting rows must be sorted alphabetically.

### Input file format

The first line of input file contains of two integers o number of tables T and number of conditions D.

Starting from the second line there are T tables represented with number of rows RN and number of columns CN in the first line of a table, which is followed by RN lines consisting of exactly CN characters each. D lines with conditions follow the whole set of tables.

### Output file format

Output file contains result rows, one row per line. No input query will produce more than 1000 rows.

### Constraints

1 ≤ T ≤ 26, 1 ≤ D ≤ 50, 1 ≤ CN ≤ 9, 1 ≤ RN ≤ 1000.

### Sample tests

No. Input file (input.txt) Output file (output.txt)
1
2 2
3 2
AX
BX
BY
2 3
ACD
BCC
a1=b1
a2=X

AXACD
BXBCC


## Problem T. Hamming Problem ≡

 Author: Far-Eastern Subregional Time limit: 3 sec Input file: input.txt Memory limit: 8 Mb Output file: output.txt

### Statement

For each three prime numbers p1, p2 and p3, letis define Hamming sequence Hi(p1, p2, p3), i = 1,... as containing in increasing order all the natural numbers whose only prime divisors are p1, p2 or p3. For example, H(2, 3, 5) = 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27,... So H5(2, 3, 5)=6.

### Input file format

In the single line of input file there are space-separated integers p1 p2 p3 i.

### Output file format

The output file must contain the single integer - Hi(p1, p2, p3).

### Constraints

All numbers in input and output are less than 1018.

### Sample tests

No. Input file (input.txt) Output file (output.txt)
1
7 13 19 100
26590291

## Problem U. Circular Area ≡

 Author: Far-Eastern Subregional Time limit: 3 sec Input file: input.txt Memory limit: 8 Mb Output file: output.txt

### Statement

Your task is to write a program, which, given two circles, calculates the area of their intersection with the accuracy of two digits after decimal point.

### Input file format

In the single line of input file there are space-separated real numbers x1 y1 r1 x2 y2 r2. They represent center coordinates and radii of two circles.

### Output file format

The output file must contain single real number — the area.

### Sample tests

No. Input file (input.txt) Output file (output.txt)
1
20.0 30.0 15.0 40.0 30.0 30.0
608.37

1.102s 0.012s 53