## Problem A. Topological sorting ≡

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

### Statement

You are to write a program that performs a topological sorting of a directed graph. Graph contains N vertices, numbered with integers from 1 to N, and M edges.

In other words, given a partial order on numbers from 1 to N, your program must produce some linear order on these numbers which does not conflict with the given partial order.

### Input file format

Input file contains two integers N and M, followed by M pairs of integers. Integers in each pair are different, and represent starting and ending vertex of a graph edge.

These pairs may also be considered comparisons where the first number precedes the second one.

### Output file format

Output file must contain a permutation of integers from 1 to N — numbers of vertices sorted in topological order. (That is, representing a linear order.) If ordering is not possible, output file must contain a single number 1.

### Constraints

0 ≤ N, M ≤ 100000

### Sample tests

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

## Problem B. Bipartite graph ≡

 Author: StdAlg (adapted by T. Chistyakov, A. Klenin) Time limit: 2 sec Input file: input.txt Memory limit: 64 Mb Output file: output.txt

### Statement

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 N M, then M pairs of integers ai bi describing the edges of the graph.

### Output file format

Output BIPARTITE if the graph is bipartite or NO if it is not.

### Constraints

1 ≤ N ≤ 100000, 0 ≤ M ≤ 1000000

### Sample tests

No. Input file (input.txt) Output file (output.txt)
1
3 2
1 2  1 3
BIPARTITE
2
4 6
1 2  2 3  3 4  4 1  1 3  2 4
NO

## Задача C. Модули ≡

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

### Условие

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

Когда все программисты сдали в отдел свою работу, выяснилось, что некоторым модулям для правильного функционирования требуются другие модули, при этом если i-тому модулю нужен j-тый, то и наоборот j-тому модулю нужен i-тый. Вам, как одному из программистов отдела, поручено написать программу, которая по сведениям о связях между модулями определила бы, сколько минимальных программ можно из них собрать. Минимальной считается программа, которую нельзя разделить на более мелкие части.

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

Входной файл содержит числа N и M — соответственно число модулей и связей между ними, за которыми следуют M пар чисел ai aj, означающие, что i-тый и j-тый модули не могут функционировать друг без друга.

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

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

### Ограничения

1 ≤ N ≤ 100000, 0 ≤ M ≤ 106

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

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

## Задача D. Почтовая реформа ≡

• задачи
 Входной файл: mail.in Ограничение времени: 4 сек Выходной файл: mail.out Ограничение памяти: 256 Мб

### Условие

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

Недавно образованное почтовое агентство "Экс-Федя" предлагает уникальную услугу — коллективную посылку. Эта услуга позволяет отправлять посылки жителям всех городов на каком-либо пути по цене обычной посылки. Удивительно, но пользоваться такой услугой стали только волшебники Флатландии, которые стали в большом количестве отправлять друг другу магические кактусы. Агентство столкнулось с непредвиденной проблемой: как известно, все волшебники живут в башнях и мало того, что не строят в них лестницы, так еще время от времени меняют их высоту. Поэтому, чтобы доставить посылку волшебнику, который живет в башне высотой h, курьеру агентства требуется иметь с собой не менее h метров веревки.

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

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

Первая строка входного файла содержит число n — количество городов в Флатландии (1 ≤ n ≤ 50000). Во второй строке находится n положительных чисел, не превосходящих 105 — высоты башен в городах. В следующих n1 строках содержится по два числа ui и vi — описание i-й дороги, 1 ≤ ui, vi ≤ n, ui ≠ vi. В следующий строке содержится число k — количество запросов (1 ≤ k ≤ 100000). В следующих k строках содержатся описания запросов в следующем формате:
• Уведомление от волшебника из города i о том, что высота его башни стала равна h, имеет вид ! i h, 1 ≤ i ≤ n, 1 ≤ h ≤ 105.
• Запрос от курьера о выдаче веревки для доставки посылок во все города на пути от i до j включительно имеет вид ? i j, 1 ≤ i, j ≤ n.

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

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

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

Входной файл (mail.in) Выходной файл (mail.out)
1
3
1 2 3
1 3
2 3
5
? 1 2
! 1 5
? 2 3
! 3 2
? 1 2

3
3
5

2
1
100
5
! 1 1
? 1 1
! 1 1000
? 1 1
! 1 1

1
1000

0.170s 0.006s 19