During a battle, Sheldor the conqueror notices that his cities are in the form of a Directed Acyclic Graph, i.e, all the roads are one-way and there is no sequence of roads starting from a city that comes back into it.
City 1 is completely under Sheldor's control and he uses it as the base shelter for his troops. He intends to send a number of troops to City 30. How many distinct paths could these troops take?
Input File: Link
Input Format and Details:
u vin that order. This means that there is a directed edge from