Задача C. Граф, но не Монте-Кристо ≡
| Автор: | Антон Карабанов | Ограничение времени: | 1 сек | |
| Входной файл: | Стандартный вход | Ограничение памяти: | 64 Мб | |
| Выходной файл: | Стандартный выход | |||
| Максимальный балл: | 100 |
Условие
Наталья Васильевна — учитель информатики. Она замечательно объясняет материал, многие ее ученики набирают 100 баллов на ЕГЭ. Сегодня ей нужно повторить с ребятами задачу о поиске путей в графе. Помогите составить программу, вычисляющую ответ на поставленную задачу: на рисунке — схема дорог, связывающих города. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города A в указанный город?
Формат входных данных
Первая строка входного файла содержит два натуральных числа, записанных через пробел: n — количество городов и m — количество дорог. В следующих m строках через пробел расположены две заглавных английских буквы — описание дороги в формате "откуда куда". Гарантируется непротиворечивость входных данных, отсутствие петель и циклов в графе, а также кратных дорог. Гарантируется, что все дороги ведут из города, обозначенного "меньшей" (в лексикографическом смысле) буквой в город, обозначенный "большей" буквой. Не гарантируется связность графа.
Формат выходных данных
Выведите одно неотрицательное целое число — количество различных путей из города A в город, обозначенный n-й буквой английского алфавита.
Ограничения
1 ≤ n ≤ 26
Система оценки и описание подзадач
Баллы за каждый тест начисляются независимо.
Пояснение к примеру
Примеры тестов
| № | Стандартный вход | Стандартный выход |
|---|---|---|
| 1 | |
|