Задача A. Бюрократия

Автор:StdAlg   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:8 Мб
Выходной файл:output.txt  

Условие

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

Будем считать, что чиновники занумерованы целыми числами от 1 до N. Тот факт, что для посещения чиновника с некоторым номером, требуется справка от чиновника с другим номером, будем называть "условием".

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

Входной файл содержит числа N и M - количество чиновников и "условий" соответственно. Далее следуют M пар целых чисел (ai, bi), каждая из которых обозначает, что для посещения чиновника с номером bi нужно иметь справку от чиновника с номером ai. Пар, состоящих из двух одинаковых чисел, нет.

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

Выведите в выходной файл N целых чисел - одну из возможных последовательностей посещения чиновников. Если такой последовательности не существует (бывает же и такое!), выведите 1.

Ограничения

1 ≤ N ≤ 100000; 0 ≤ M ≤ 100000

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

Входной файл (input.txt) Выходной файл (output.txt)
1
4 3
1 2
1 3
3 4
1 3 2 4

Problem B. Shortest Spanning Tree

Author:StdAlg   Time limit:1 sec
Input file:input.txt   Memory limit:16 Mb
Output file:output.txt  

Statement

You are to write a program that receives a weighted undirected graph and finds length of its shortest spanning tree.

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 next M lines contain three integers describing an edge — numbers of vertices, connected by an edge and its weight respectively. All weights are positive. There is at most one edge connecting two vertices.

Output file format

Output file must contain a signle integer number — length of the SST. If it is impossible to construct spanning tree, output file must contain −1.

Constraints

1 ≤ N ≤ 1000 All weights are less or equal 1000.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
3 3
1 2 10
2 3 10
3 1 10
20

Problem C. Eulerian cycle

Author:StdAlg   Time limit:1 sec
Input file:input.txt   Memory limit:64 Mb
Output file:output.txt  

Statement

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.

Constraints

1 ≤ N, M ≤ 100000

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
3 3
1 2
2 3
3 1
1 2 3 1

Задача D. Звёздный путь (ROI-2013)

Автор:Жюри ROI-2013   Ограничение времени:3 сек
Входной файл:expedition.in   Ограничение памяти:256 Мб
Выходной файл:expedition.out  

Условие

Экспедиция готовится отправиться в путь на космическом корабле нового поколения. Планируется последовательно посетить N планет звёздной системы — от планеты Земля до планеты Победа. Планеты пронумерованы от 1 до N в порядке их посещения, Земля имеет номер 1, а Победа — номер N.

Для перелёта между планетами корабль может использовать любой тип топлива, существующий в звёздной системе. Перед началом экспедиции корабль находится на планете Земля, и бак корабля пуст. Существующие типы топлива пронумерованы целыми числами, на планете с номером i можно заправиться только топливом типа ai. При посещении i-й планеты можно заправиться, полностью освободив бак от имеющегося топлива и заполнив его топливом типа ai.

На каждой планете станция заправки устроена таким образом, что в бак заправляется ровно столько топлива, сколько потребуется для перелёта до следующей планеты с топливом такого же типа. Если далее такой тип топлива не встречается, заправляться на этой планете невозможно. Иначе говоря, после заправки на i-й планете топлива хватит для посещения планет от (i + 1)-й до j-й включительно, где j — минимальный номер планеты, такой что j > i и aj = ai. Для продолжения экспедиции дальше j-й планеты корабль необходимо снова заправить на одной из этих планет.

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

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

В первой строке входного файла записано число N — количество планет.

Во второй строке входного файла записано N целых чисел a1, a2, …, aN — типы топлива на планетах.

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

В первой строке выходного файла выведите единственное число K — минимальное количество заправок, которые нужно произвести.

Во второй строке выведите K чисел, разделённых пробелами, — номера планет, на которых требуется заправиться. Номера планет требуется выводить в порядке времени заправок.

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

Ограничения

2 ≤ N ≤ 300 000;

1 ≤ ai ≤ 300 000;

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

Входной файл (expedition.in) Выходной файл (expedition.out)
1
7
1 3 2 1 3 2 3
3
1 3 5
2
7
4 3 2 4 3 2 1
0

Задача E. Перестройка

Автор:Russian Code Cup 2012   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

В некоторой стране было ровно N городов и M дорог между ними. При этом в этой стране дорожная система была устроена следующим образом:

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

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

Теперь правительство задумалось о том, сколько существует способов провести реформу. Помогите ему.

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

Первая строка содержит два целых числа N и M. Следующие M строк содержат два числа ai, bi  — номера городов, которые соединяет i-я дорога.

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

Выведите одно целое число  — количество способов провести реформу.

Ограничения

1 ≤ N ≤ 105

0 ≤ M ≤ 2 ⋅ 105

1 ≤ ai, bi ≤ N, ai ≠ bi


0.177s 0.071s 19