Отдел инновационных технологий фирмы "Division Computers" решил, что повысить
производительность в написании программ можно, если использовать модульное
программирование, т.е. когда когда каждый программист пишет свою часть отдельно.
Когда все программисты сдали в отдел свою работу, выяснилось, что
некоторым модулям для правильного функционирования требуются другие модули, при
этом если i-тому модулю нужен j-тый, то и наоборот j-тому модулю нужен i-тый.
Вам, как одному из программистов отдела, поручено написать программу, которая
по сведениям о связях между модулями определила бы, сколько минимальных программ можно
из них собрать. Минимальной считается программа, которую нельзя разделить на более мелкие части.
Формат входного файла
Входной файл содержит числа N и M — соответственно число модулей и связей между ними, за
которыми следуют M пар чисел aiaj, означающие, что i-тый и j-тый модули
не могут функционировать друг без друга.
Формат выходного файла
Выходной файл должен содержать число получившихся после сборки программ.
В некотором государстве различные официальные вопросы решаются с помощью мощного бюрократического аппарата.
Программист Василий хочет получить разрешение на открытие своей фирмы, но он еще не знает с какими сложностями
ему придется столкнуться! Для того, чтобы оформить разрешение на свою деятельность Василий должен получить
определенный набор справок, каждую из которых выдает специально предназначенный для этого чиновник.
Задача усложняется тем, что многие из этих госслужащих не дают свои справки просто так. А именно, для
каждого из них известно, справки от каких других чиновников нужно иметь при себе, чтобы получить справку от этого.
Чтобы помочь Василию, напишите программу, которая выдаст последовательность посещения чиновников, которая бы
гарантировала, что никто из них ему не откажет.
Будем считать, что чиновники занумерованы целыми числами от 1 до N. Тот факт, что для посещения чиновника
с некоторым номером, требуется справка от чиновника с другим номером, будем называть "условием".
Формат входного файла
Входной файл содержит числа N и M - количество чиновников и "условий" соответственно.
Далее следуют M пар целых чисел (ai, bi), каждая из которых обозначает, что для посещения чиновника с
номером bi нужно иметь справку от чиновника с номером ai. Пар, состоящих из двух одинаковых чисел, нет.
Формат выходного файла
Выведите в выходной файл N целых чисел - одну из возможных последовательностей посещения чиновников.
Если такой последовательности не существует (бывает же и такое!), выведите −1.
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.
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.
