Способы задания графа

ID 33471. Степени вершин

Неориентированный граф задан матрицей смежности. Найдите степени всех вершин графа.

Формат входных данных
В первой строке вводится число n  (1 ≤ n ≤ 100) – количество вершин в графе. Далее идет n строк по n чисел, каждое из которых равно 0 или 1, – его матрица смежности.

Формат выходных данных
Выведите n чисел – степени вершин графа (по одному числу в строке). 

ID 38632. Издевательство

Штирлиц ехал на машине, увидел голосующего Бормана, и проехал мимо. Через некоторое время он снова увидел голосующего Бормана, и снова проехал мимо. Вскоре он опять увидел голосующего Бормана.
 - Издевается! - подумал Борман.
 - Кольцевая! - догадался Штирлиц.

В городе N площадей. Любые две площади соединены между собой ровно одной дорогой с двусторонним движением. В этом городе живет Штирлиц. У Штирлица есть хобби - он любит воскресным утром выйти из дома, сесть в машину, выбрать какой-нибудь кольцевой маршрут, проходящий ровно по трем площадям (то есть сначала он едет с какой-то площади на какую-то другую, потом - на третью, затем возвращается на начальную, и опять едет по этому маршруту). Он воображает, что где-то на этом пути стоит Борман. И так вот ездит Штирлиц все воскресенье, пока голова не закружится, и радуется...

Естественно, что Штирлицу хочется проезжать мимо точки, в которой, как он воображает, стоит Борман, как можно чаще. Для этого, естественно, выбранный Штирлицем маршрут должен быть как можно короче. Напишите программу, которая выберет оптимальный для Штирлица маршрут.

Входные данные
В первой строке задается  число N (3 <= N <= 100). В последующих строках содержится матрица NxN расстояний между площадями (число в позиции i,j обозначает длину дороги, соединяющей i-ую и j-ую площади). Все числа в матрице (кроме стоящих на главной диагонали) - натуральные, не превышающие 1000. Матрица симметрична относительно главной диагонали, на главной диагонали стоят 0.

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

Примеры

ID 44035. Схема дорог

Дед Мороз составляет схему дорог, по которой можно будет кратчайшим образом посетить N городов. Для простоты он пронумеровал все города номерами 1,..., N. Города соединены M количеством дорог. I-я дорога (1<=i<=M) соединяет город Ai и город Bi. Прежде чем построить оптимальный маршрут Дед Мороз хочет знать с какими городами связан каждый город. Помогите Деду Морозу.
Выведите N строк следующим образом.

• Пусть di - количество городов, непосредственно связанных с городом i (1<=i<=N), и этими городами будут города a_i,1, ..., ai,di,перечисленных в порядке возрастания.
• I-я строка (1<=i<=N) должна содержать di+1 целое число: di, ai,1,...,ai,di в указанном порядке, разделенные пробелами.

Примеры

ID 45463. Проверка на неориентированность

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

Примеры

5
0 0 1 0 0 
0 0 1 0 1 
1 1 0 0 0 
0 0 0 0 0 
0 1 0 0 0 

ID 45475. Петли

По заданной матрице смежности неориентированного графа определите, содержит ли он петли.

Примеры

ID 45488. Подсчет количества ребер неориентированного графа

Простой неориентированный граф задан матрицей смежности. Найдите количество ребер в графе.

Примеры

5
0 0 1 0 0 
0 0 1 0 1 
1 1 0 0 0 
0 0 0 0 0 
0 1 0 0 0 

ID 45489. Подсчет количества ребер ориентированного графа

Ориентированный граф задан матрицей смежности. Найдите количество ребер в графе.

Примеры

5
0 0 0 0 0 
0 0 0 0 1 
1 1 0 0 0 
0 0 0 0 0 
0 0 0 0 0 

ID 45531. От матрицы смежности к списку ребер, неориентированный вариант

Простой неориентированный граф задан матрицей смежности, выведите его представление в виде списка ребер.

Примеры

5
0 0 1 0 0 
0 0 1 0 1 
1 1 0 0 0 
0 0 0 0 0 
0 1 0 0 0 

1 3
2 3
2 5

ID 45532. От списка ребер к матрице смежности, неориентированный вариант

Простой неориентированный граф задан списком ребер, выведите его представление в виде матрицы смежности.

Входные данные
На вход программы поступают числа n ( 1≤ n ≤100 ) – количество вершин в графе и m ( 1≤ m ≤ n(n−1)/2 ) – количество ребер. Затем следует m пар чисел – ребра графа.
Выходные данные
Выведите матрицу смежности заданного графа.

Примеры

5 3
1 3
2 3
2 5

0 0 1 0 0 
0 0 1 0 1 
1 1 0 0 0 
0 0 0 0 0 
0 1 0 0 0 

ID 45533. От матрицы смежности к списку ребер, ориентированный вариант

Ориентированный граф задан матрицей смежности, выведите его представление в виде списка ребер.

Примеры

 5 
0 0 0 0 0
0 0 0 0 1
1 1 0 0 0
0 0 0 0 0
0 0 0 0 0 

2 5 
3 1
3 2

ID 45534. От списка ребер к матрице смежности, ориентированный вариант

Простой неориентированный граф задан списком ребер, выведите его представление в виде матрицы смежности.

Входные данные
На вход программы поступают числа n ( 1≤ n ≤100 ) – количество вершин в графе и m ( 1≤ m ≤ n(n−1) ) – количество ребер. Затем следует m пар чисел – ребра графа.
Выходные данные
Выведите матрицу смежности заданного графа.

Примеры

5 3
1 3
2 3
5 2

0 0 1 0 0 
0 0 1 0 0 
0 0 0 0 0 
0 0 0 0 0 
0 1 0 0 0 

ID 45631. Проверка на наличие параллельных ребер, неориентированный вариант

Неориентированный граф задан списком ребер. Проверьте, содержит ли он параллельные ребра.
Входные данные
Сначала вводятся  числа n ( 1≤ n ≤100 ) – количество вершин в графе и m ( 1≤ m ≤10000 ) – количество ребер.
Затем следует m пар чисел – ребра графа.

Примеры

5 3
1 3
2 3
2 5

NO

ID 45633. Проверка на наличие параллельных ребер, ориентированный вариант

Ориентированный граф задан списком ребер. Проверьте, содержит ли он параллельные ребра.
Входные данные
Сначала вводятся  числа n ( 1≤ n ≤100 ) – количество вершин в графе и m ( 1≤ m ≤10000 ) – количество ребер.
Затем следует m пар чисел – ребра графа.

Примеры

5 3
1 3
2 3
2 5

NO

ID 45649. Степени вершин по спискам ребер

Неориентированный граф задан списком ребер. Найдите степени всех вершин графа.
Входные данные
Сначала вводятся числа n ( 1≤ n ≤ 100 ) – количество вершин в графе и m ( 1≤ m ≤ n(n−1)/2 ) – количество ребер.
Затем следует m пар чисел – ребра графа.

Примеры

5 3
1 3
2 3
2 5

1
2
2
0
1

ID 45655. Полустепени вершин

Ориентированный граф задан матрицей смежности. Найдите полустепени захода и полустепени исхода всех вершин графа.
Входные данные
Сначала вводится число n ( 1≤ n ≤100 ) – количество вершин в графе, а затем n строк по n чисел, каждое из которых равно 0 или 1, – его матрица смежности.

Примеры

5
0 0 0 0 0 
0 0 0 0 1 
1 1 0 0 0 
0 0 0 0 0 
0 0 0 0 0 

1
0
1
1
0
2
0
0
1
0

ID 45656. Полустепени вершин по спискам ребер

Ориентированный граф задан списком ребер. Найдите степени всех вершин графа.
Входные данные
Сначала вводятся числа n ( 1 ≤ n ≤ 100 ) –  количество вершин в графе и m ( 1≤ m ≤ n(n−1) ) – количество ребер. Затем следует m пар чисел – ребра графа.

Примеры

5 3
2 5
3 1
3 2

1
0
1
1
0
2
0
0
1
0

ID 45657. Истоки и стоки

Напомним, что вершина ориентированного графа называется истоком, если в нее не входит ни одно ребро и стоком, если из нее не выходит ни одного ребра.
Ориентированный граф задан матрицей смежности. Найдите все вершины графа, которые являются истоками, и все его вершины, которые являются стоками.
Входные данные
Сначала вводится число n ( 1≤ n ≤100 ) – количество вершин в графе, а затем n строк по n чисел, каждое из которых равно 0 или 1, – его матрица смежности.
Выходные данные
Вначале выведите k – число истоков в графе и затем k чисел – номера вершин, которые являются истоками, в возрастающем порядке. 
Затем выведите информацию о стоках в том же порядке.

Примеры

5
0 0 0 0 0 
0 0 0 0 1 
1 1 0 0 0 
0 0 0 0 0 
0 0 0 0 0 

2
3
4
3
1
4
5

ID 45658. Регулярный граф

Неориентированный граф называется регулярным, если все его вершины имеют одинаковую степень.
Для заданного списком ребер графа проверьте, является ли он регулярным.
Входные данные
Сначала вводятся числа n ( 1≤ n ≤ 100 ) – количество вершин в графе и m ( 0≤ m ≤ n(n−1)/2 ) – количество ребер.
Затем следует m пар чисел – ребра графа.
Выходные данные
Выведите  «YES», если граф является регулярным, и «NO» в противном случае.

Примеры

5 0

YES

ID 45659. Полный граф

Неориентированный граф с кратными рёбрами называется полным, если любая пара его различных вершин соединена хотя бы одним ребром.
Для заданного списком ребер графа проверьте, является ли он полным.
Входные данные
Сначала вводятся числа n ( 1≤ n ≤ 100 ) – количество вершин в графе и m ( 0≤ m ≤ n(n−1)/2 ) – количество ребер.
Затем следует m пар чисел – ребра графа.
Выходные данные
Выведите  «YES», если граф является полным, и «NO» в противном случае.

Примеры

5 18
1 2
1 3
1 3
1 4
1 4
1 4
1 5
1 5
2 3
2 4
2 4
2 5
3 4
3 4
3 4
3 5
3 5
4 5

YES

ID 45660. Полуполный граф

Ориентированный граф называется полуполным, если между любой парой его различных вершин есть хотя бы одно ребро.
Для заданного списком ребер графа проверьте, является ли он полуполным.
Входные данные
Сначала вводятся числа n ( 1≤ n ≤ 100 ) – количество вершин в графе и m ( 0≤ m ≤ n(n−1)/2 ) – количество ребер.
Затем следует m пар чисел – ребра графа.
Выходные данные
Выведите  «YES», если граф является полуполным, и «NO» в противном случае.

Примеры

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

NO

ID 45661. Турнир

Ориентированный граф называется турниром, если между любой парой его различных вершин существует ровно одно ребро.
Для заданного списком ребер графа проверьте, является ли он турниром.
Входные данные
Сначала вводятся числа n ( 1≤ n ≤ 100 ) – количество вершин в графе и m ( 0≤ m ≤ n(n−1)/2 ) – количество ребер.
Затем следует m пар чисел – ребра графа.
Выходные данные
Выведите  «YES», если граф является турниром, и «NO» в противном случае.

Примеры

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

YES

ID 45662. Транзитивность неориентированного графа

Напомним, что граф называется транзитивным, если всегда из того, что вершины u и v соединены ребром и вершины v и w соединены ребром следует,
что вершины u и w соединены ребром.
Проверьте, что заданный неориентированный граф является транзитивным.
Входные данные
Сначала вводятся числа n ( 1≤ n ≤ 100 ) – количество вершин в графе и m ( 0≤ m ≤ n(n−1)/2 ) – количество ребер.
Затем следует m пар чисел – ребра графа.
Выходные данные
Выведите  «YES», если граф является транзитивным, и «NO» в противном случае.

Примеры

5 1
2 5

YES

ID 45663. Транзитивность ориентированного графа

Напомним, что ориентированный граф называется транзитивным, если для любых трех различных вершин u, v и w из того,
что из u в вершину v ведет ребро и из вершины v в вершину w ведет ребро, следует, что из вершины u в вершину w ведет ребро.
Проверьте, что заданный ориентированный граф является транзитивным.
Входные данные
Сначала вводятся числа n ( 1≤ n ≤ 100 ) – количество вершин в графе, а затем n строк по n чисел,
каждое из которых равно 0 или 1, – его матрица смежности.
Выходные данные
Выведите  «YES», если граф является транзитивным, и «NO» в противном случае.

Примеры

5
0 0 0 0 0 
0 0 0 0 0 
0 0 0 0 0 
0 0 0 0 0 
0 0 0 0 0 

YES

ID 45664. Обрати меня!

Мальчик Вася очень любит разворачивать ориентированные графы. Помогите ему в этом.
Входные данные
Во входном файле записано число N (1 ≤ N  ≤ 50000) - количество вершин в графе.
В следующих N строках записан граф в виде списков смежности: в i-ой строке, в порядке возрастания, записаны номера вершин,
в которые идут ребра из i-ой вершины. Нумерация начинается с единицы. Гарантируется, что ребер в графе не более 50000.
Выходные данные
Выведите развернутый граф в том же формате, что и исходный.

Примеры

4
2 3
3

2

4

1 4
1 2

ID 45665. Степени вершин

Неориентированный граф задан матрицей смежности. Найдите степени всех вершин графа.
Входные данные
Сначала вводятся числа n ( 1≤ n ≤ 100 ) – количество вершин в графе, 
а затем n строк по n чисел, каждое из которых равно 0 или 1, – его матрица смежности.
Выходные данные
Выведите n чисел – степени вершин графа.

Примеры

5
0 0 1 0 0 
0 0 1 0 1 
1 1 0 0 0 
0 0 0 0 0 
0 1 0 0 0 

1
2
2
0
1

ID 46183. Матрица смежности из списков

Напишите программу, которая строит матрицу смежности графа на основе списков смежности для каждой вершины.
Входные данные
В первой строке вводится количество вершин графа N ( 1 ≤ N ≤ 1000 ).
В следующих N строках записаны списки смежности для каждой вершины – номера вершин, в которые существуют исходящие рёбра из данной вершины.
Выходные данные
Программа должна вывести матрицу смежности для заданного графа.

Примеры

5
2 3 4
1 3 5
1 2 4
0
2 4

0 1 1 1 0 
1 0 1 0 1 
1 1 0 1 0 
0 0 0 0 0 
0 1 0 1 0 

ID 46184. Списки смежности из матрицы

Напишите программу, которая строит списки смежности для каждой вершины графа на основе его матрицы смежности.
Входные данные
В первой строке вводится количество вершин графа N ( 1 ≤ N ≤ 1000 ).
В следующих N строках записано по N чисел, разделённых пробелами – элементы матрицы смежности графа.
Выходные данные
Программа должна вывести списки смежности для каждой вершины графа в порядке возрастания их номеров.
Номера вершин в каждом списке разделены пробелами и идут в порядке возрастания.
Нумерация начинается с единицы. Если из вершины не выходит ни одно ребро, вместо списка нужно вывести число 0.

Примеры

5
0 1 1 1 0
1 0 1 0 1
1 1 0 1 0
0 0 0 0 0
0 1 0 1 0

2 3 4 
1 3 5 
1 2 4 
0
2 4 

ID 46184. Списки смежности из матрицы

Напишите программу, которая строит списки смежности для каждой вершины графа на основе его матрицы смежности.
Входные данные
В первой строке вводится количество вершин графа N ( 1 ≤ N ≤ 1000 ).
В следующих N строках записано по N чисел, разделённых пробелами – элементы матрицы смежности графа.
Выходные данные
Программа должна вывести списки смежности для каждой вершины графа в порядке возрастания их номеров.
Номера вершин в каждом списке разделены пробелами и идут в порядке возрастания.
Нумерация начинается с единицы. Если из вершины не выходит ни одно ребро, вместо списка нужно вывести число 0.

Примеры

5
0 1 1 1 0
1 0 1 0 1
1 1 0 1 0
0 0 0 0 0
0 1 0 1 0

2 3 4 
1 3 5 
1 2 4 
0
2 4 

ID 23371. Мишина машина (В', В)

ID 49242. От матрицы смежности к списку ребер, ориентированный вариант

Ориентированный граф задан матрицей смежности, выведите его представление в виде списка ребер.

На вход программы поступает число n (1 ≤ n ≤ 100) – количество вершин  графа, а затем n строк по n чисел, каждое из которых равно 0 или 1, – его матрица смежности. 

ID 49243. От списка ребер к матрице смежности, ориентированный вариант

Простой ориентированный граф задан списком ребер, выведите его представление в виде матрицы смежности.

На вход программы поступают числа n ( 1 ≤ n ≤ 100) - количество вершин в графе и m (1 ≤ m ≤ n(n-1)) – количество ребер. Затем следует m пар чисел – ребра графа.

Выведите матрицу смежности заданного графа.

ID 33132. От списка ребер к матрице смежности, неориентированный вариант

ID 33131. От матрицы смежности к списку ребер, неориентированный вариант

ID 33129. Петли

ID 33130. Проверка на неориентированность

ID 22017. Города и дороги

Примечание

ID 22018. Светофорчики-1

ID 22019. Цветной дождь

ID 49448. Мафия

В городе Лост-Хевен произошла серия загадочных преступлений. Жители напуганы и не знают, кому можно доверять. Местный Шериф позвал на помощь знаменитого детектива Нормана, чтобы тот помог ему найти главаря мафии. 
Норман принялся за дело и опросил всех жителей города. В итоге он теперь знает, кто кого боится. 
Норман знает, что главным подозреваемым будет тот житель города, который удовлетворяет следующим условиям:
1) Подозреваемый никого не боится.
2) Все остальные жители боятся подозреваемого. 
3) Существует ровно один такой человек, который удовлетворяет первым двум условиям.
Вы - программист, который помогает Норману. Норман дал вам информацию в виде списка, кто кого боится.  Помогите Норману определить главного подозреваемого. 

Формат входных данных
В первой строке записано натуральное число N - количество жителей города Лост-Хевен (1 <= N <= 1000). Во второй строке содержится неотрицательное число K (0 <= K <= 104) - количество записей сделанных Норманом после опроса всех жителей города. В следующих K строках записано по два числа (ai, bi) - обозначающие то, что i-й житель a боится жителя b (1 <= ai, bi <= n, ai не равно bi, каждая пара (ai, bi) уникальна).

Формат выходных данных
Выведите номер подозреваемого. Если выявить подозреваемого не представляется возможным, то в ответе укажите число -1.

ID 30719. Вирус

В лаборатории биоинформатики ученые проводят эксперименты по распространению искусственно созданных вирусов. Для эксперимента используется специальная лабораторная установка, представляющая собой таблицу из n × m ячеек. В каждую ячейку помещается живая клетка. Ученые заражают вирусом некоторые клетки, всего исходно заражается не более 8 клеток.
Каждую секунду среди незараженных клеток, имеющих зараженную клетку в соседней по стороне ячейке, ровно одна клетка заражается вирусом.
Ученые заинтересовались, какие конфигурации зараженных клеток могут получиться через t секунд. Для начала они хотят посчитать число таких конфигураций. Помогите им это сделать.

Формат входных данных
В первой строке входного файла находятся целые числа n, m и t (1 ≤ n, m ≤ 100, 1 ≤ t ≤ 6) — размеры таблицы и количество секунд. Каждая из следющих n строк содержит m символов. Символ «.» означает, что в изначальной конфигурации клетка не заражена, а символ «*» — что заражена. Количество «*» в таблице не превышает 8. Гарантируется, что незараженных клеток в исходной конфигурации не меньше t.

Формат выходных данных
Выведите количество различных возможных конфигураций таблицы после t секунд.
 

ID 33310. Файловый менеджер

ID 51088. Электрички на перегонах не меняют

На пригородной железной дороге N станций и M соединяющих их перегонов. Любые две станции соединены не более чем одним перегоном. Сеть перегонов устроена так, что, отправившись от любой станции, можно вернуться на нее, только проехав хотя бы один перегон дважды. На железной дороге организовано движение электричек. Каждая электричка ходит в обоих направлениях по своему маршруту между двумя конечными станциями и останавливается на всех промежуточных станциях

Для удобства пассажиров руководство железной дороги решило ввести новую систему оплаты проезда. По этой системе каждой станции присваивается некоторое целое число, называемое тарифным номером этой станции. Стоимость проезда между двумя станциями без пересадок определяется модулем разности тарифных номеров этих станций. Тарифные номера станций вдоль маршрута каждой электрички должны изменяться монотонно, то есть при движении в каком-либо направлении строго возрастать и, следовательно, строго убывать при движении в обратном направлении. Это обеспечивает рост стоимости проезда с увеличением количества пройденных перегонов.

Требуется написать программу, которая назначит каждой станции тарифный номер.
 

	4 станции, 3 перегона: 1-4, 2-4, 3-4 Маршруты: 1-4-2, 2-4-3, 3-4-1.   Ответ: решения нет
	5 станций, 4 перегона: 1-5, 2-5, 3-5, 4-5 Маршруты: 1-5-2, 2-5-3, 3-5-4, 4-5-1.   Ответ: решение есть; например, следующее: номер станции: 1 2 3 4 5 тарифный номер: 1 4 1 5 3   Замечание: тарифные номера разных станций могут совпадать.

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

В первой строке входных данных содержатся два целых числа: N — количество станций (2 ≤ N ≤ 100 000), и M — количество перегонов между ними (1 ≤ M ≤ N – 1). В последующих M строках записаны пары целых чисел a, b (a ≠ b, 1 ≤ a ≤ N, 1 ≤ b ≤ N), означающие наличие перегона между станциями a и b. За ними в отдельной строке записано единственное целое положительное число K — количество маршрутов электричек. В последующих K строках идут описания маршрутов электричек, по одному на строке. Каждое описание представляет собой последовательность целых чисел — номеров всех станций маршрута в порядке одного из двух возможных направлений следования электрички. Описание маршрута заканчивается числом 0.

Все номера станций в описании маршрута различны. Количество станций в каждом маршруте не менее двух. Любые две последовательные станции в маршруте каждой электрички соединены перегоном. Суммарное количество станций в описаниях всех маршрутов не превосходит 200 000. Могут быть станции и перегоны, через которые не проходит ни одна электричка.
 

В первую строку выведите «NO», если искомого назначения тарифных номеров не существует. В противном случае в первую строку выведите «YES», а в следующей строке — N целых положительных чисел, где i-е число — тарифный номер i-й станции. Тарифный номер каждой станции должен находиться в диапазоне от 1 до N.

Если существует несколько решений, необходимо вывести любое из них.

ID 53943. Метро

Женя получил письмо от Леши со словесным описанием схемы метро в его городе. Метро содержит одну кольцевую линию. Каждая из остальных линий пересекается с кольцевой не более чем в двух местах, причем в точках пересечения организованы пересадочные станции. В одном месте кольцевую линию могут пересекать сразу несколько линий, имеющих общую пересадочную станцию.

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

Для каждой пересадочной станции Леша описал, какие линии на ней пересекаются, и указал порядок расположения пересадочных станций на кольцевой линии. Он утверждает, что все линии расположены на одной глубине и других пересечений, помимо пересадочных узлов, не имеют. Чтобы проверить это утверждение, Женя стал по словесному описанию рисовать схему метро, но у него не получилось.

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

На рисунке приведена возможная схема метро, соответствующая второму примеру.

Формат входных данных
В первой строке содержится число \(k\) — количество линий метро в городе (\(1 \le k \le 10\)). Все линии пронумерованы от 0 до \(k - 1\), кольцевая линия имеет номер 0. Во второй строке записано число \(n\) — количество пересадочных станций. Каждая из следующих \(n\) строк описывает линии, пересекающиеся на соответствующей пересадочной станции, причем сначала следуют описания пересадочных станций, расположенных на кольцевой линии, в порядке их расположения на ней. Описание каждого узла начинается с количества пересекающихся в нем линий, затем следуют номера линий.

Формат выходных данных
Выведите слово YES, если по описанию можно построить схему метро, и NO в противном случае.

ID 53948. Шоссе

Во Флатландии \(n\) городов, расположенных в различных точках плоскости. Известно, что никакие три города не лежат на одной прямой.

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

Завод, выполняющий этот госзаказ, подготовил проект сети шоссе. Проект представляет собой описание \(n - 1\) шоссе. Каждое шоссе задается городами, которые оно соединяет. В целях секретности вместо названий городов в проекте были использованы коды — числа от 1 до \(n\).

Однако когда дело дошло до реализации проекта, выяснилось, что документ, в котором было указано соответствие номеров городам, утерян. Поскольку проект приурочен к пятисотлетию культурной столицы Флатландии, переделывать проект полностью оказалось невозможно. Поэтому было решено установить некоторое новое соответствие номеров городам.

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

Ваша задача — таким образом сопоставить числам от 1 до \(n\) города, чтобы после реализации проекта шоссе не пересекались вне городов, которые они соединяют.

Формат входных данных
В первой строке содержится целое число \(n\) — количество городов во Флатландии (\(2 \le n \le 1500\)).

Далее следует \(n\) описаний городов. Описание каждого города состоит из двух строк. Первая строка содержит название города — строку, состоящую из символов с ASCII-кодами от 33 до 127. Названия различных городов не совпадают. Длина названия города не превышает 60 символов. Вторая строка описания города содержит два целых числа \(x\) и \(y\) — координаты города. Координаты не превышают \(10^4\) по абсолютной величине.

Далее следуют \(n - 1\) строк, которые описывают проект строительства сети шоссе в его текущем состоянии. Каждая строка содержит по два целых числа — номера городов, соединенных шоссе в проекте. Никакое шоссе в проекте не соединяет город сам с собой, никакие два города не соединены более чем одним шоссе.

Формат выходных данных
Выведите \(n\) строк, \(i\)-я из этих строк должна содержать название города, который следует сопоставить числу \(i\) в проекте. Если решений несколько, выведите любое.

Если решения не существует, выведите <<No solution>>.

Иллюстрация к примеру

ID 54149. Подсчет количества ребер неориентированного графа

Простой неориентированный граф задан матрицей смежности. Найдите количество ребер в графе.

Входные данные
На вход программы поступает число n ( 1≤n≤100) – количество вершин в графе, а затем n строк по n чисел, каждое из которых равно 0 или 1, – его матрица смежности.

Выходные данные
Выведите одно число – количество ребер заданного графа.

ID 54152. Подсчет количества ребер ориентированного графа

Ориентированный граф задан матрицей смежности. Найдите количество ребер в графе.

Входные данные
На вход программы поступает число n ( 1≤n≤100 ) – количество вершин в графе, а затем n строк по n чисел, каждое из которых равно 0 или 1, – его матрица смежности.

Выходные данные
Выведите одно число – количество ребер заданного графа.

ID 54159. Проверка на наличие параллельных ребер, неориентированный вариант

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

Входные данные
Сначала вводятся  числа n ( 1≤n≤100) – количество вершин в графе и m ( 1≤m≤10,000 ) – количество ребер. Затем следует m пар чисел – ребра графа.

Выходные данные
Выведите  «YES», если граф содержит параллельные ребра, и «NO» в противном случае.

ID 54161. Проверка на наличие параллельных ребер, ориентированный вариант

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

Сначала вводятся числа n ( 1≤n≤1001≤𝑛≤100 ) – количество вершин в графе и m ( 1≤m≤10,0001≤𝑚≤10,000 ) – количество ребер. Затем следует m пар чисел – ребра графа.

Выведите  «YES», если граф содержит параллельные ребра, и «NO» в противном случае.

ID 54163. Степени вершин по спискам ребер

Неориентированный граф задан списком ребер. Найдите степени всех вершин графа.

Входные данные
Сначала вводятся числа n ( 1≤n≤100 ) – количество вершин в графе и \(m (1 \leq m \leq n (n - 1) / 2)\)  – количество ребер. Затем следует m пар чисел – ребра графа.

Выходные данные
Выведите n чисел – степени вершин графа.

ID 54167. Полустепени вершин

Ориентированный граф задан матрицей смежности. Найдите полустепени захода и полустепени исхода всех вершин графа.

Входные данные
Сначала вводится число n ( 1≤n≤100) – количество вершин в графе, а затем n строк по n чисел, каждое из которых равно 0 или 1, – его матрица смежности.

Выходные данные
Выведите  n пар чисел – для каждой вершины сначала выведите полустепень захода и затем полустепень исхода.

ID 54171. Полустепени вершин по спискам ребер

Ориентированный граф задан списком ребер. Найдите степени всех вершин графа.

Входные данные
Сначала вводятся числа n ( 1≤n≤100 ) –  количество вершин в графе и \(m (1 \leq m \leq n (n-1))\) – количество ребер. Затем следует m пар чисел – ребра графа.

Выходные данные
Выведите  n пар чисел – для каждой вершины сначала выведите полустепень захода и затем полустепень исхода.

ID 54176. Истоки и стоки

Напомним, что вершина ориентированного графа называется истоком, если в нее не входит ни одно ребро и стоком, если из нее не выходит ни одного ребра.

Ориентированный граф задан матрицей смежности. Найдите все вершины графа, которые являются истоками, и все его вершины, которые являются стоками.

Входные данные
Сначала вводится число n ( 1≤n≤100) – количество вершин в графе, а затем n строк по n чисел, каждое из которых равно 0 или 1, – его матрица смежности.

Выходные данные
Вначале выведите k – число истоков в графе и затем k чисел – номера вершин, которые являются истоками, в возрастающем порядке. Затем выведите информацию о стоках в том же порядке.

ID 54180. Регулярный граф

Неориентированный граф называется регулярным, если все его вершины имеют одинаковую степень. Для заданного списком ребер графа проверьте, является ли он регулярным.

Входные данные
Сначала вводятся числа n ( 1≤n≤100) – количество вершин в графе и \(m (0 \leq m \leq n (n - 1)/2)\)  – количество ребер. Затем следует m пар чисел – ребра графа.

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

ID 54187. Полуполный граф

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

Входные данные
Сначала вводятся числа n ( 1≤n≤100 ) – количество вершин в графе и \(m (1 \leq m \leq n (n-1))\)  – количество ребер. Затем следует m пар чисел – ребра графа.

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

ID 54183. Полный граф

Неориентированный граф с кратными рёбрами называется полным, если любая пара его различных вершин соединена хотя бы одним ребром. Для заданного списком ребер графа проверьте, является ли он полным.

Входные данные
Сначала вводятся числа n ( 1≤n≤100 ) – количество вершин в графе и \(m ( 1 \leq m \leq n (n-1)/2)\)  – количество ребер. Затем следует m пар чисел – ребра графа.

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

ID 54188. Турнир

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

Входные данные
Сначала вводятся числа n ( 1≤n≤100 ) – количество вершин в графе и \(m ( 1 \leq m \leq n (n-1))\)  – количество ребер. Затем следует m пар чисел – ребра графа.

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

ID 54189. Транзитивность неориентированного графа

Напомним, что граф называется транзитивным, если всегда из того, что вершины u и v соединены ребром и вершины v и w соединены ребром следует, что вершины u и w соединены ребром.

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

Входные данные
Сначала вводятся числа n ( 1≤n≤100 ) – количество вершин в графе и \(m (1 \leq m \leq n (n-1)/2)\)  – количество ребер. Затем следует m пар чисел – ребра графа.

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

ID 54191. Транзитивность ориентированного графа

Напомним, что ориентированный граф называется транзитивным, если для любых трех различных вершин u, v и w из того, что из u в вершину v ведет ребро и из вершины v в вершину w ведет ребро, следует, что из вершины u в вершину w ведет ребро.

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

Входные данные
Сначала вводится число n ( 1≤n≤100 ) – количество вершин в графе, а затем n строк по n чисел, каждое из которых равно 0 или 1, – его матрица смежности.

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

ID 38191. Метро

Метрополитен состоит из нескольких линий метро. Все станции метро в городе пронумерованы натуральными числами от 1 до N. На каждой линии расположено несколько станций. Если одна и та же станция расположена сразу на нескольких линиях, то она является станцией пересадки и на этой станции можно пересесть с любой линии, которая через нее проходит, на любую другую (опять же проходящую через нее).

Напишите программу, которая по данному вам описанию метрополитена определит, с каким минимальным числом пересадок можно добраться со станции A на станцию B. Если данный метрополитен не соединяет все линии в одну систему, то может так получиться, что со станции A на станцию B добраться невозможно, в этом случае ваша программа должна это определить.

Входные данные
Сначала вводится число N — количество станций метро в городе (2≤N≤100). Далее следует число M — количество линий метро (1≤M≤20). Далее идет описание M линий. Описание каждой линии состоит из числа P_i — количество станций на этой линии (2≤P_i≤50) и P_i чисел, задающих номера станций, через которые проходит линия (ни через какую станцию линия не проходит дважды).

Затем вводятся два различных числа: A — номер начальной станции, и B — номер станции, на которую нам нужно попасть. При этом если через станцию A проходит несколько линий, то мы можем спуститься на любую из них. Так же если через станцию B проходит несколько линий, то нам не важно, по какой линии мы приедем.

Выходные данные
Выведите минимальное количество пересадок, которое нам понадобится. Если добраться со станции A на станцию B невозможно, программа должна вывести одно число –1 (минус один).
 

Примеры

ID 54672. Яблоко от яблони…

У Пети в саду растет яблоня. Воодушевленный историей об Исааке Ньютоне, который, как известно, открыл закон всемирного тяготения после того, как ему на голову упало яблоко, Петя с целью повысить свою успеваемость по физике часто сидит под яблоней.

Однако, поскольку по физике у Пети твердая тройка, яблоки с его яблони падают следующим образом. В какой-то момент одно из яблок отрывается от ветки, на которой оно висит, и начинает падать строго вниз. Если в некоторый момент оно задевает другое яблоко, то то тоже отрывается от своей ветки и начинает падать вниз, при этом первое яблоко не меняет направление своего падения. Вообще, если любое падающее яблоко заденет другое яблоко на своем пути, то оно также начнет падать.

Таким образом, в любой момент каждое яблоко либо висит на ветке, либо падает строго вниз, причем все яблоки кроме первого, чтобы начать падать, должны сначала соприкоснуться с каким-либо другим падающим яблоком.

Выясните, какие яблоки упадут с Петиной яблони.

Входные данные
В первой строке вводится число N - количество яблок на Петиной яблоне (1 <= N <= 200). Следующие N строк содержат описания яблок. Будем считать все яблоки шарами. Каждое яблоко задается координатами своей самой верхней точки (той, где оно исходно прикреплено к дереву, длиной черенка пренебрежем) x_i, y_i и z_i и радиусом r_i ( -10000 <= x_i, y_i, z_i <= 10000, 1 <= r_i <= 10000, все числа целые). Гарантируется, что изначально никакие яблоки не пересекаются (даже не соприкасаются). Ось OZ направлена вверх.

Выходные данные
В первой строке выведите количество яблок, которые упадут с яблони, если начнет падать первое яблоко. В следующей строке выводите номера упавших яблок. Яблоки нумеруются, начиная с 1, в том порядке, в котором они заданы во входных данных.

ID 55000. Развлечения с измерителем

Дима обнаружил у папы на столе специальный чертежный прибор, похожий на циркуль - измеритель. Измеритель отличается от обычного циркуля тем, что в обеих его ножках находятся иголки (у обычного циркуля в одной ножке находится иголка, а в другой - грифель).

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

Вечером папа нашел лист, с которым развлекался Дима, и решил выяснить, какое расстояние между иглами измерителя Дима мог установить. Все, что знает папа - координаты дырок, проделанных иглами измерителя. Помогите Папе решить поставленную задачу.

Входные данные
В первой строке вводится число n
 - количество дырок (2 <= n <= 1000). Следующие n строк содержат по два целых числа - координаты дырок. Координаты не превышают 10⁴
 по абсолютной величине.

Выходные данные
В первой строке выведите k
 - количество различных расстояний, которые Дима мог установить между иглами измерителя. Следующие k строк должны содержать искомые расстояния, по одному вещественному числу в строке. Расстояния должны быть выведены в возрастающем порядке. Каждое число должно быть выведено с точностью не менее, чем 10^-9.

Гарантируется, что существует по крайней мере одно расстояние, которое Дима мог установить между иглами измерителя.

ID 55401. Свинки-копилки

У Васи есть N свинок-копилок, свинки занумерованы числами от 1 до N. Каждая копилка может быть открыта единственным соответствующим ей ключом или разбита.

Вася положил ключи в некоторые из копилок (он помнит, какой ключ лежит в какой из копилок). Теперь Вася собрался купить машину, а для этого ему нужно достать деньги из всех копилок. При этом он хочет разбить как можно меньшее количество копилок (ведь ему еще нужно копить деньги на квартиру, дачу, вертолет…). Помогите Васе определить, какое минимальное количество копилок нужно разбить.

Входные данные
В первой строке содержится число N — количество свинок-копилок (1≤N≤100000). Далее идет N строк с описанием того, где лежит ключ от какой копилки: в i-ой из этих строк записан номер копилки, в которой находится ключ от i-ой копилки.

Выходные данные
Выведите единственное число: минимальное количество копилок, которые необходимо разбить.

Примечание
Ключи от первой и третьей копилки лежат в копилке 2, ключ от второй — в первой, а от четвертой — в ней самой.
Чтобы открыть все копилки, достаточно разбить, например, копилки с номерами 1 и 4.
 

ID 55402. Трехцветные таблицы

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

Раскраска всех клеток таблицы (или просто сама таблица) называется правильной, если она может быть получена описанным выше способом.

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

Входные данные
Вводятся числа N и M — количество строк и столбцов таблицы (1≤N≤30, 1≤M≤30). Далее записано N строк по M чисел в каждой, задающие цвета, в которые должны быть окрашены клетки:

0 — клетка может в итоге быть любого цвета

1 — клетка должна быть синей

2 — клетка должна быть желтой

3 — клетка должна быть зеленой

Выходные данные
Выведите одно число — количество различных правильных таблиц, в которых нужные клетки покрашены в нужный цвет. Обратите внимание, что если два или более способов раскраски столбцов и строк таблицы приводят к одинаковой раскраске самой таблицы, то это нужно считать как один вариант раскраски таблицы (см. пример 2).

ID 56020. Свинки-копилки

У Васи есть N свинок-копилок, свинки занумерованы числами от 1 до N. Каждая копилка может быть открыта единственным соответствующим ей ключом или разбита.

Вася положил ключи в некоторые из копилок (он помнит, какой ключ лежит в какой из копилок). Теперь Вася собрался купить машину, а для этого ему нужно достать деньги из всех копилок. При этом он хочет разбить как можно меньшее количество копилок (ведь ему еще нужно копить деньги на квартиру, дачу, вертолет…). Помогите Васе определить, какое минимальное количество копилок нужно разбить.

Входные данные
В первой строке содержится число N — количество свинок-копилок (1≤N≤100000). Далее идет N строк с описанием того, где лежит ключ от какой копилки: в i-ой из этих строк записан номер копилки, в которой находится ключ от i-ой копилки.

Выходные данные
Выведите единственное число: минимальное количество копилок, которые необходимо разбить.

Примечание
Ключи от первой и третьей копилки лежат в копилке 2, ключ от второй — в первой, а от четвертой — в ней самой.
Чтобы открыть все копилки, достаточно разбить, например, копилки с номерами 1 и 4.
 

ID 55548. Вырезанные фигуры

Эпидемия гриппа не обошла стороной семиклассника Алешу. Скучая дома, Алеша решил вырезать фигурки из листа клетчатой бумаги. Лист состоял из M строк и N столбцов клеточек. Сначала Алеша нарисовал на листе границы фигур. Количество фигур было не меньше 2. Чтобы фигуры получались ровными, границы фигур Алеша рисовал строго по линиям имеющейся клеточной разметки листа (при этом некоторые границы фигур могли пройти по границам листа). Форма фигур могла быть любой, но при этом все фигуры были связными (фигура называется связной, если из любой ее клетки можно добраться до любой другой, ходя только по клеткам фигуры и перемещаясь каждый раз в одну из 4-х соседних по стороне клеток). Никакие две фигуры не имели общих точек, в том числе не касались углами клеток.

<>Затем Алеша вырезал нарисованные фигуры, делая разрезы только по их границам. При этом оставшаяся часть листа осталась связной (то есть не распалась на несколько частей).
Лист с вырезами Алеша отсканировал. Сканер в своей памяти по результатам сканирования построил таблицу, состоящую из нулей и единиц, из M строк и N столбцов (строки нумеруются сверху вниз от 1 до M, столбцы — слева направо от 1 до N). Каждый элемент таблицы соответствовал клеточке исходного листа. Единица обозначала, что соответствующая клетка листа осталась на месте, ноль — соответствующая клетка была вырезана.

На рис. 1 приведен пример клетчатого листа, а на рис. 2 — соответствующая ему таблица в памяти сканера:
 

• направление (0—горизонтальная, 1—вертикальная)
• (i, j) — координаты начальной клетки полосы (начальной является самая левая клетка для горизонтальной полосы, и самая верхняя — для вертикальной), i — номер строки клетки, j — номер столбца
• d — длина полосы (количество подряд стоящих единиц).

• В каждой клетке начинается не более одной полосы.
• Полосы перечислены в порядке следования их начальных клеток (клетки перечисляются по строкам сверху вниз, в строке — слева направо).
• Общее число полос не превышает 256000.

ID 55547. Юный поджигатель

На клеточном поле введена система координат так, что центр координат находится в точке пересечения линий сетки  и оси направлены вдоль линий сетки.

На этом поле выложили связную фигуру, состоящую из спичек. Использовались спички двух типов:

• Спички длины 1 выкладывались по сторонам клеток.
• Спички длины выкладывались по диагоналям клеток.