В некотором государстве различные официальные вопросы решаются с помощью мощного бюрократического аппарата.
Программист Василий хочет получить разрешение на открытие своей фирмы, но он еще не знает с какими сложностями
ему придется столкнуться! Для того, чтобы оформить разрешение на свою деятельность Василий должен получить
определенный набор справок, каждую из которых выдает специально предназначенный для этого чиновник.
Задача усложняется тем, что многие из этих госслужащих не дают свои справки просто так. А именно, для
каждого из них известно, справки от каких других чиновников нужно иметь при себе, чтобы получить справку от этого.
Чтобы помочь Василию, напишите программу, которая выдаст последовательность посещения чиновников, которая бы
гарантировала, что никто из них ему не откажет.
Будем считать, что чиновники занумерованы целыми числами от 1 до N. Тот факт, что для посещения чиновника
с некоторым номером, требуется справка от чиновника с другим номером, будем называть "условием".
Формат входного файла
Входной файл содержит числа N и M - количество чиновников и "условий" соответственно.
Далее следуют M пар целых чисел (ai, bi), каждая из которых обозначает, что для посещения чиновника с
номером bi нужно иметь справку от чиновника с номером ai. Пар, состоящих из двух одинаковых чисел, нет.
Формат выходного файла
Выведите в выходной файл N целых чисел - одну из возможных последовательностей посещения чиновников.
Если такой последовательности не существует (бывает же и такое!), выведите − 1.
Вам задан связный ориентированный граф с N вершинами и M ребрами.
Найдите компоненты сильной связности заданного графа и топологически отсортируйте его конденсацию.
Формат входного файла
Граф задан во входном файле следующим образом: первая строка содержит числа N и M.
Каждая из следующих M строк содержат описание ребра - два целых числа из диапазона от 1 до
N - номера начала и конца ребра.
Формат выходного файла
На первой строке выведите число K - количество компонент сильной связности в заданном графе.
На следующей строке выведите N чисел - для каждой вершины выведите номер компоненты сильной связности,
которой принадлежит эта вершина. Компоненты сильной связности должны быть занумерованы таким образом,
чтобы для любого ребра номер компоненты сильной связности его начала не превышал номера компоненты
сильной связности его конца.
В заданном корневом дереве найдите вершины, максимально удалённые
от корня. Расстоянием между вершинами считается количество рёбер в пути.
Формат входного файла
В первой строке задано n "--- количество вершин в дереве.
В следующих n − 1 строках заданы вершины, являющиеся предками
вершин 2, 3, …, n. Вершина 1 является корнем дерева.
Формат выходного файла
В первой строке выведите максимальное расстояние от корня до остальных
вершин дерева.
Во второй строке выведите, сколько вершин дерева находятся от корня
на таком расстоянии.
В третьей строке выведите номера этих вершин через пробел
в порядке возрастания.
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.
Телекоммуникационная сеть крупной IT-компании содержит n серверов,
пронумерованных от 1 до n. Некоторые пары серверов соединены двусторонними каналами
связи, всего в сети m каналов. Гарантируется, что сеть серверов устроена таким образом, что
по каналам связи можно передавать данные с любого сервера на любой другой сервер,
возможно с использованием одного или нескольких промежуточных серверов.
Множество серверов A называется отказоустойчивым, если при недоступности
любого канала связи выполнено следующее условие. Для любого не входящего в это
множество сервера X существует способ передать данные по остальным каналам на сервер X
хотя бы от одного сервера из множества A.
На рис. 1 показан пример сети и отказоустойчивого множества из серверов с
номерами 1 и 4. Данные на сервер 2 можно передать следующим образом. При
недоступности канала между серверами 1 и 2 — с сервера 4, при недоступности канала
между серверами 2 и 3 — с сервера 1. На серверы 3 и 5 при недоступности любого канала
связи можно по другим каналам передать данные с сервера 4.
Рис. 1. Пример сети и отказоустойчивого множества серверов.
В рамках проекта группе разработчиков компании необходимо разместить свои
данные в сети. Для повышения доступности данных и устойчивости к авариям разработчики
хотят продублировать свои данные, разместив их одновременно на нескольких серверах,
образующих отказоустойчивое множество.
Чтобы минимизировать издержки, необходимо выбрать минимальное по количеству серверов отказоустойчивое множество. Кроме того, чтобы узнать, насколько гибко устроена сеть, необходимо подсчитать количество способов
выбора такого множества, и поскольку это количество способов может быть большим,
необходимо найти остаток от деления этого количества способов на число 109 + 7.
Требуется написать программу, которая по заданному описанию сети определяет
следующие числа: k — минимальное количество серверов в отказоустойчивом множестве
серверов, c — остаток от деления количества способов выбора отказоустойчивого множества
из k серверов на число 109 + 7
Формат входного файла
Первая строка входного файла содержит целые числа n и m — количество серверов и
количество каналов связи соответственно.
Следующие m строк содержат по два целых числа и описывают каналы связи между
серверами. Каждый канал связи задается двумя целыми числами: номерами серверов,
которые он соединяет.
Гарантируется, что любые два сервера соединены напрямую не более чем одним
каналом связи, никакой канал не соединяет сервер сам с собой, и для любой пары серверов
существует способ передачи данных с одного из них на другой, возможно с использованием
одного или нескольких промежуточных серверов.
Формат выходного файла
Выведите два целых числа, разделенных пробелом: k — минимальное число серверов
в отказоустойчивом множестве серверов, c — количество способов выбора
отказоустойчивого множества из k серверов, взятое по модулю 109 + 7
Ограничения
2 ≤ n ≤ 200000, 1 ≤ m ≤ 200000
Система оценки и описание подзадач
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой
подзадачи и необходимых подзадач успешно пройдены.
Подзадача
Баллы
Дополнительные ограничения
Необходимые подзадачи
n
m
1
25
2 ≤ n ≤ 10
1 ≤ m ≤ 45
2
27
2 ≤ n ≤ 200000
m = n − 1
3
28
2 ≤ n ≤ 1000
1 ≤ m ≤ 5000
1
4
21
2 ≤ n ≤ 200000
1 ≤ m ≤ 200000
1, 2, 3
Описание подзадач и системы оценивания
По запросу сообщается результат окончательной проверки на каждом тесте.
Пояснение к примеру
В приведённом примере отказоустойчивыми являются следующие множества из двух серверов:
{1, 3}, {1, 4}, {1, 5}.
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.
Ура! Влад закончил создание своей собственной игры в виртуальной реальности.
Для продвижения игры он собирается провести турнир, в котором примут участие N киберспортсменов.
Турнир будет проходить по следующей системе: в каждом туре выбирается пара игроков,
выигравший остаётся в турнире, а проигравший выбывает.
В конце турнира остаётся один игрок — победитель.
В игре присутствуют некоторые проблемы с производительностью, и Влад об этом знает.
Он хочет, чтоб потенциальные покупатели игры увидели игру в лучшем свете.
Поэтому Влад подобрал M таких пар игроков ai и bi,
что игрок c номером ai всегда побеждает игрока с номером bi,
и во время матчей в этих парах не возникает проблем с производительностью.
Во избежание непредвиденных ситуация он хочет так составить расписание турнира так,
чтобы он знал победителей всех матчей заранее и в конце турнира остался ровно один игрок.
Формат входного файла
Первая строка входного файла содержит числа N и M.
Следующие M строк содержат пары чисел ai и bi.
Гарантируется, что не существует такой пары i и j, что ai = bj и bi = aj.
Формат выходного файла
Если невозможно провести турнир так, как хочет Влад, необходимо вывести No.
Иначе первая строка выходного файла должна содержать Yes, а
следующие далее N − 1 строк — описание матчей в порядке их проведения.
По два числа на строку: первое число — номер победившего в очередном матче игрока,
второе число — номер проигравшего игрока.
Если существует несколько правильных ответов, выведите любой из них.
