Задача A. Дерево ≡

Условие

Дан неориентированный граф. Проверьте, является ли он деревом.

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

В первой строке входного файла заданы через пробел два целых числа n и m — количество вершин и рёбер в графе, соответственно. В следующих m строках заданы рёбра; i-я из этих строк содержит два целых числа u_i и v_i через пробел — номера концов i-го ребра. Граф не содержит петель и кратных рёбер.

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

В первой строке выходного файла выведите YES, если граф является деревом, и NO в противном случае.

Ограничения

1 ≤ n ≤ 10⁵

0 ≤ m ≤ 10⁵

1 ≤ u_i, v_i ≤ n

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

3 2
1 2
1 3

YES

3 3
1 2
2 3
3 1

NO

Задача B. Лабиринт токсиков ≡

Условие

Денис посетил вечеринку спортивных программистов в Точке кипения, где участники обсуждали различные алгоритмы. В ходе обсуждения возник спор о задачах на BFS. Одни считали их интересными, другие - душными. Через какой-то время спор почти дошел до драки между участниками, после чего любители задач на BFS назвали своих противников “токсиками” и решили закрыть их в Точке кипения. В свою очередь Точка кипения представляет собой лабиринт.

Точка кипения представлена матрицей размерностью n×m. Она может содержать следующие символы:

• ‘.’ - пустая клетка;
• ‘#’ - стена;
• ‘S’ - любитель BFS;
• ‘T’ -токсик.

Любители BFS хотят заблокировать противников, а именно заменить некоторые пустые клетки на стены так, чтобы все любители BFS смогли добраться до выхода, а все токсики остались заперты в Точке кипения.

Клетки, которые изначально содержат символы 'S' или 'T', не могут быть заблокированы, но через них можно проходить.

Помогите Денису определить, можно ли заблокировать некоторые пустые клетки в Точке кипения так, чтобы ВСЕ любители BFS смогли выйти, но при этом токсики бы не смогли. Люди могут передвигаться на соседние клетки в Точке кипения по вертикали и по горизонтали. Учтите, что разрешается не блокировать клетки вовсе и блокировать выход из точки кипения. Гарантируется, что выход из лабиринта всегда представляет собой пустую клетку.

Формат входных данных

Первая строка содержит одно целое число t (1 ≤ t ≤ 1000) - количество наборов входных данных.

Для каждого набора входных данных:

• первая строка содержит два целых числа n и m (1 ≤ n, m ≤ 100) - размерность лабиринта;
• в каждой из следующих n строк записано m символов. Символ '.' обозначает пустую клетку, '#' - стену, 'S' - любителя BFS, а 'T' - токсика.

Формат выходных данных

Для каждого набора входных данных выведите "YES" или "NO", в зависимости от того, можно ли заменить некоторые пустые клетки на стены, чтобы удовлетворить описанным ограничениям.

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

2
3 3
S..
...
T..
2 2
ST
T.

YES
NO

Задача C. Лабиринт ≡

Условие

Дан квадратный лабиринт, размером N × N, координаты точки входа и точки выхода. Определите минимальное расстояние от входа до выхода.

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

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

В выходном файле должно содержаться единственное число — минимальное расстояние. Лабиринт проходим.

Ограничения

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

4 1 1 4 1
..#.
..#.
..#.
....

9

Problem D. Dijkstra ≡

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

Output file format

Constraints

Sample tests

5 3 1
1 2 5
1 3 7
3 4 10

0 5 7 17 -1

Задача E. Водовод на о. Русский ≡

Условие

При строительстве нового кампуса ДВФУ на о. Русском по дну пролива был проложен водовод с материка на остров. К сожалению, после завершения строительства все чертежи были утеряны, а строители разъехались. Чтобы восстановить карту водовода, были проведены гидрографические работы.

Была составлена прямоугольная карта залива, разбитая на ячейки. Левый столбец ячеек примыкает к материку, а правый — к острову. По результатам работ каждая ячейка была помечена символом '#' (по ячейке может проходить водовод) или '.' — водовод по ячейке точно не проходит.

Известно, что водовод представляет собой последовательность ячеек, имеющих общую сторону. Первая его ячейка находится в первом столбце клеток карты, последняя — в последнем. Водовод не проходит дважды через одну и ту же ячейку.

Дана карта, составленная по результатам работ. Необходимо определить, можно ли однозначно восстановить водовод по карте.

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

Первая строка входного файла содержит размеры карты — высоту H и ширину W. Далее следует H строк по W символов в каждой — карта.

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

Если положение водовода может быть однозначно восстановлено, то выведите сначала слово YES, а затем набор чисел, содержащих описание самого водовода. Первое число в описании обозначает количество ячеек водовода, n, за которым следует n пар чисел вида r_i, c_i, обозначающих номер строки и номер столбца очередной ячейки (строки и столбцы нумеруются с единицы).

Если существует несколько способов восстановить положение водовода, то выведите сначала слово MULTIPLE, а затем два различных описания водовода в любом порядке. Если существует более двух вариантов, выведите любые два из них.

Если водовод восстановить невозможно, выведите единственное слово NO.

Ограничения

2 ≤ H, W ≤ 200

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

4 5
...##
##...
.####
...#.

YES
6  2 1  2 2  3 2  3 3  3 4  3 5 

3 6
#.###.
###.##
......

MULTIPLE
9  1 1  2 1  2 2  2 3  1 3  1 4  1 5  2 5  2 6
8  2 1  2 2  2 3  1 3  1 4  1 5  2 5  2 6

3 6
..###.
###.##
..###.

MULTIPLE
8  2 1  2 2  2 3  1 3  1 4  1 5  2 5  2 6
8  2 1  2 2  2 3  3 3  3 4  3 5  2 5  2 6

3 3
...
.##
...

NO

Задача F. Слон Пахом и разработка RPG ≡

Условие

Слон Пахом создаёт новую RPG, для игры ему потребовался уровень-лабиринт. Лабиринт содержит n × m платформ, n рядов по m платформ. Платформы бывают трёх видов:

1. Коридоры. В зависимости от ориентации обозначаются или символом "-" (находясь на такой платформе можно, пройти только влево или вправо) или "|" (находясь на такой платформе, можно пройти только вверх или вниз).
2. Перекрёстки. Обозначаются символом "+" (можно пройти в любую сторону).
3. Стены. Обозначаются символом "#" (по ним нельзя пройти).

С платформы на платформу можно перейти, только если платформы стыкуются между собой. Во время похождения по коридору игрок может повернуть платформу, на которой он находится, на 90 градусов и продолжить прохождение в любом направлении, или же оставить платформу нетронутой и пройти дальше.

Слон Пахом сгенерировал несколько лабиринтов, но теперь начал сомневаться в проходимости этих лабиринтов. Кроме того, Пахом считает, что поворот платформы запутывает игрока, поэтому для он хочет определить, можно ли пройти лабиринт, а если можно, то он хочет найти минимальное количество поворотов платформ, необходимое для прохождения лабиринта.

Слон Пахом не справился с поставленной задачей и просит вас написать программу для определения минимального необходимого количества поворотов платформ для прохождения лабиринта, если лабиринт проходимый.

Формат входных данных

Первая строка входных данных содержит два целых числа n и m. Следующие n строк содержат по m символов каждая — описание лабиринта.

Формат выходных данных

Первая строка выходных данных должна содержать "YES", если лабиринт проходимый, в противном случае "NO".

Если лабиринт проходимый, то следующая строка должна содержать целое число k — минимальное количество поворотов, необходимое для прохождения лабиринта.

Ограничения

1 ≤ n, m ≤ 10³

Описание подзадач и системы оценивания

Решения, работающие для n = 1, оцениваются из 30 баллов. Баллы выставляются за каждый успешно пройденный тест.

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

5 5
+++++
+++++
+++++
+++++
+++++

YES
0

1 8
+-------

YES
0

1 8
+------|

NO

5 6
|-----
|-###-
#|---#
####|#
+++#|-

YES
5

1 1
#

NO