9. Все дороги

Имеется n городов пронумерованных с 1 до n и m соединяющих дорог. Найти количество всевозможных маршрутов с города с номером start до города с номером finish. Маршруты без циклов.

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

Во входном файле в первой строке записаны два числа n и m, задающие соответственно количество городов и количество дорог (1≤n≤100, 0≤m≤10000), со второй строки заданы m пар чисел - дороги. В последней строке заданы два числа - start и finish.

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

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

Примеры

input.txt	output.txt	Примечание
4 6 1 2 1 3 1 5 2 3 3 4 4 5 1 3	3	Имеем следующие пути: 1 2 3 1 3 5 4 3

10. Линия электропередач

Администрация улуса планирует проведение новой линии электропередач. В улусе всего N поселков. Требуется сделать такой план сети электропередач, чтобы общая длина проводов была минимальна.

Ввод:

Первая строка входного файла содержит два целых числа: ./V — количество поселков в улусе (2≤N≤100) и М — количество возможных соединений поселков (1≤М≤1500). Все улусы пронумерованы от 1 до N. Следующие М строк содержат информацию о возможных соединениях — номера двух поселков, которые могут быть соединены, и длина провода, которая требуется, чтобы соединить их. Эта длина — натураль­ное число.

Вывод:

Вывести одно число – общая длина провода.

Пример:

input.txt	output.txt
5 7 1 2 4 1 3 1 1 4 2 1 5 1 2 3 2 3 5 5 4 5 3	6

11. Два города

Имеется n городов пронумерованных с 1 до n и m соединяющих их дорог. Расстояния между любыми двумя городами равны 1. Которая из двух городов A и B наиболее удалена от города с номером 1. Если они на одинаковом расстоянии, напечатать любой из них.

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

В первой строке заданы n и m, со второй строки пары целых чисел – номера вершин образующих ребро. В последней строке заданы вершины A и B.

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

Вывести одно число – номер вершины (A или B) наиболее удаленного от города номер 1.

Пример

input.txt	output.txt
5 5 1 5 2 5 2 4 3 4 4 5 3 5	3

12. Два не связанных города

В республике N городов пронумерованных с 1 до N. M городов связаны дорогами. Найти два города не связанных дорогами.

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

Во входном файле записаны сначала два числа N и M, задающие соответственно количество вершин и количество ребер (1≤N≤100, 1≤M≤10000), а затем перечисляются ребра. Каждое ребро задается номерами вершин, которые оно соединяет.

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

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

связности.

Пример

input.txt	output.txt
6 4 1 2 2 3 2 4 5 6	1 5