Задача A. Модули ≡

Условие

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

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

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

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

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

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

Ограничения

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

3 1
2 3

2

Задача B. КПК ≡

Условие

Хакер Вася решил собрать карманный персональный компьютер (КПК). Согласно найденной им в Интернет инструкции компьютер собран правильно тогда, когда ток из каждой микросхемы может пройти в каждую и притом единственным путем.

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

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

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

Ограничения

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

3 1
2 3

1
2 3
1
1 2

Задача C. Текстовый редактор ≡

Условие

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

Текст, с которым работает редактор Билла, представляет собой набор строк. Строки состоят из печатных символов (с ASCII-кодами больше 32) и пробелов. Строка никогда не начинается пробелом и не заканчивается им. Слово — это часть строки, не содержащая пробелов и ограниченная слева и справа пробелами или концами строки. Пользователь может перемещать курсор с помощью восьми операций:

• Влево. Курсор перемещается на один символ влево. Если курсор стоит в начале строки, то он не сдвигается.
• Вправо. Курсор перемещается на один символ вправо. Если курсор стоит в конце строки, то он не сдвигается.
• Вверх. Курсор перемещается на одну строку вверх. Если текущая строка первая, то курсор не сдвигается. Если после перемещения курсор выходит за пределы строки, то он устанавливается на ее последний символ.
• Вниз. Курсор перемещается на одну строку вниз. Если текущая строка последняя, то курсор не сдвигается. Если после перемещения курсор выходит за пределы строки, то он устанавливается на ее последний символ.
• В начало строки. Перемещение на первый символ текущей строки.
• В конец строки. Перемещение на последний символ текущей строки.
• На одно слово влево. Если курсор находится внутри слова, то он перемещается на его первый символ. Если же курсор находится на символе пробела или на первом символе слова, то он перемещается на начало предыдущего слова. Если текущее слово — первое, то курсор окажется на первом символе строки.
• На одно слово вправо. Курсор перемещается на начало следующего слова. Если текущее слово последнее в строке, то курсор перемещается на последний символ строки.

Любая операция, кроме двух последних, требует одного нажатия на клавишу. Перемещение на слово влево и на слово вправо требует двух нажатий (Ctrl+left, Ctrl+right).

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

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

Ограничения

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

3 10
ababaca baca
abcde
ab abc abcde

5

1 1
begin write(a+b); end.

8

Задача D. Дайте мне справку, что вам нужна справка... ≡

Условие

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

Требуется написать программу, выдающую способ получения справки от M-го чиновника, требующий минимального общего количества справок.

Рекомендуется рассмотреть частичные решения для следующих случаев

• Администрация состоит из одного или двух чиновников.
• Бюрократия в администрации отсутствует — все чиновники выдают справки, ничего не требуя предъявлять.

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

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

Ограничения

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

1 1
0

1 1

2 1
1 2
1 1

0

2 1
1 2
0

2 2 1