Problem A. 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 B. Hype spreading ≡

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

Statement

One famous car race takes place on a stadium with a racetrack. Spectators watching the race sit on a stand consisting of H rows with W seats each. During the race, some seats are occupied by spectators, and others are empty.

Marketing research demonstrated that if one spectator will loudly shout out a nicely rhymed slogan, spectators on seats located immediately to the left, right, above and below him will repeat it. Their neighbors, in turn, will catch up, and the slogan will spread throughout the stand.

An advertisement company invented a new slogan and wants it to spread among as many spectators as possible. To simulate "spontaneous" appearance of the slogan the company hired an agent who will move to one of the unoccupied seats and shout the slogan from there.

You program must determine the position of the agent which will result in maximum slogan penetration.

Input file format

Input file contains integers W H in the first line, followed by H lines of W characters each.

Each character is either a '.' (ASCII 46) or '#' (ASCII 35), denoting free and occupied seat correspondingly.

There is at least one free seat.

Output file format

Output file must contain two integers — x y, denoting seat number and row number for the agent to take. Rows are numbered starting from 1, top to bottom. Seats are numbered starting from 1, left to right. If there are several optimal solutions, output any of them.

Constraints

2 ≤ W, H ≤ 2000

Sample tests

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


3 2

Задача C. Бюрократия ≡

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

Условие

В некотором государстве различные официальные вопросы решаются с помощью мощного бюрократического аппарата. Программист Василий хочет получить разрешение на открытие своей фирмы, но он еще не знает с какими сложностями ему придется столкнуться! Для того, чтобы оформить разрешение на свою деятельность Василий должен получить определенный набор справок, каждую из которых выдает специально предназначенный для этого чиновник. Задача усложняется тем, что многие из этих госслужащих не дают свои справки просто так. А именно, для каждого из них известно, справки от каких других чиновников нужно иметь при себе, чтобы получить справку от этого. Чтобы помочь Василию, напишите программу, которая выдаст последовательность посещения чиновников, которая бы гарантировала, что никто из них ему не откажет.

Будем считать, что чиновники занумерованы целыми числами от 1 до N. Тот факт, что для посещения чиновника с некоторым номером, требуется справка от чиновника с другим номером, будем называть "условием".

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

Входной файл содержит числа N и M - количество чиновников и "условий" соответственно. Далее следуют M пар целых чисел (ai, bi), каждая из которых обозначает, что для посещения чиновника с номером bi нужно иметь справку от чиновника с номером ai. Пар, состоящих из двух одинаковых чисел, нет.

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

Выведите в выходной файл N целых чисел - одну из возможных последовательностей посещения чиновников. Если такой последовательности не существует (бывает же и такое!), выведите −1.

Ограничения

1 ≤ N ≤ 100000; 0 ≤ M ≤ 100000

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

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

Problem D. 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
0.068s 0.004s 13