0266. Дорога в университет

Имя входного файла:	paths.in
Имя выходного файла:	paths.out
Ограничение по времени:	2 s
Ограничение по памяти:	64 megabytes

В университете учится очень много людей из нашего города. Некоторые из них живут рядом с корпусом, к котором у них идут занятия, а некоторым приходится далеко ехать, чтобы приобщиться к источнику знаний. Иногда транспорт подводит и студенты опаздывают. К сожалению, проблема опаздывающего транспорта не может быть решена математическими методами, поэтому ей мы заниматься не можем. А жаль. Тогда займемся другой проблемой: Пусть весь город представлен своей картой, на которой точками отмечены остановки транспорта, а отрезками, соединяющими точки - какие-то пути между остановками. Понятно, что пересечения и взаимное расположение отрезков на плоскости дела не меняют: выйти из транспорта можно только на остановке. Да, и еще пусть пути между остановками будут направленными, т. е. ехать по ним можно будет только в одну сторону. Теперь пусть заданы 2 остановки: та, с которой студент Петя начинает ехать в университет и та, недалеко от которой университет находится. Петю интересует, сколькими способами он может доехать до университета, причем ездить он может сколько угодно, может проезжать через одну и ту же остановку несколько раз, даже может не выходить на остановке у университета, если ему хочется ездить еще.

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

В первой строке входного файла заданы число N и M - количество остановок в городе и количество путей между остановками (1 ≤ N ≤ 1000, 1 ≤ M ≤ 100000). Далее следует M строк по два числа, которые описывают начало и конец пути от одной остановки до другой (ехать можно только из начала в конец, но не наоборот). Гарантируется, что не будет пути, который соединяет остановку с самой собой. В последней строке даны 2 числа: остановка у Петиного дома и остановка у университета.

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

Вывести количество путей от дома Пети к университету. Два пути считаются различными, если они различаются количеством либо порядком остановок в них, либо самими остановками, которые в них входят. Если путей бесконечно много необходимо выдать слово "Infinite". Если же путей конечное число, но при этом их больше, чем 2*10⁹, нужно выдать "Too many paths".

Пример:

paths.in	paths.out
3 3 1 2 2 3 1 3 1 3	2

Источник: Первенство первокурсника ПетрГУ. Осень 2006.

Обсудить       Отправить решение



Версия для печати