You are to write a program that receives an unweighted undirected graph and writes all its vertices in
order of increasing distance from given vertex S.
Distance between vertices A and B is the length of the shortest path from A to B.
If there are several vertices such that their distances to S are equal,
they may be printed in arbitrary order.
Input file format
Input file contains three integers N, M and S.
Vertices are numbered with integer numbers from 1 to N. M is the number of edges,
S is the starting vertice.
Each of next M lines contain pair of integers — numbers of vertices connected by an edge.
Output file format
Output file must contain sequence of vertex numbers sorted by increasing distance from S.
If some vertex is not reachable from S, output must contain a single number −1.
В некотором государстве различные официальные вопросы решаются с помощью мощного бюрократического аппарата.
Программист Василий хочет получить разрешение на открытие своей фирмы, но он еще не знает с какими сложностями
ему придется столкнуться! Для того, чтобы оформить разрешение на свою деятельность Василий должен получить
определенный набор справок, каждую из которых выдает специально предназначенный для этого чиновник.
Задача усложняется тем, что многие из этих госслужащих не дают свои справки просто так. А именно, для
каждого из них известно, справки от каких других чиновников нужно иметь при себе, чтобы получить справку от этого.
Чтобы помочь Василию, напишите программу, которая выдаст последовательность посещения чиновников, которая бы
гарантировала, что никто из них ему не откажет.
Будем считать, что чиновники занумерованы целыми числами от 1 до N. Тот факт, что для посещения чиновника
с некоторым номером, требуется справка от чиновника с другим номером, будем называть "условием".
Формат входного файла
Входной файл содержит числа N и M - количество чиновников и "условий" соответственно.
Далее следуют M пар целых чисел (ai, bi), каждая из которых обозначает, что для посещения чиновника с
номером bi нужно иметь справку от чиновника с номером ai. Пар, состоящих из двух одинаковых чисел, нет.
Формат выходного файла
Выведите в выходной файл N целых чисел - одну из возможных последовательностей посещения чиновников.
Если такой последовательности не существует (бывает же и такое!), выведите −1.
For a given undirected graph with N vertices and M edges
you need to figure out whether the graph is bipartite or no.
NOTE. A graph is called bipartite if it's possible
to split its vertices into two non-empty sets so that there is no edges
between any two vertices from the same set.
Input file format
Input file contains integers NM, then M
pairs of integers aibi describing the edges of the graph.
Output file format
Output BIPARTITE if the graph is bipartite or NO if it is not.
