TAP2013C  Little RedCap
[The original version of this problem (in Spanish) can be found at http://www.dc.uba.ar/events/icpc/download/problems/tap2013problems.pdf]
Once upon a time there was a very joyous girl who was called Little RedCap because she always wore a red riding cap. RedCap enjoyed a lot her strolls in the woods, during which she collected berries in her small basket to offer them to her grandmother, who was known to prepare the most delicious pies of all the region. However, RedCap definitely did not enjoy the perils of the woods, and in particular the Big Bad Wolf who was always hungry and prying.
One day, RedCap decides to go from her home to that of her grandmother, collecting berries on the way and trying to make her journey in the safest possible way. RedCap's house is in a clearing at the westernmost point of the woods, her grandmother's house is in another clearing at the easternmost point, and inside the woods between them there are some other clearings containing berry trees. The woods are very dense, so the only way to go through them is using the pathways between the clearings, which fortunately RedCap knows very well. In order not to get lost, RedCap always moves through pathways that take her to a point strictly to the east of the point where she is. In order not to be caught by the wolf RedCap finds it imperative to avoid an ambush, and for that reason she always has in mind the number of different paths that take her from her current position to her grandmother's home.
A path in the woods is a sequence of clearings ordered from west to east, such that each clearing is connected with the next by a pathway. A path to the house of RedCap's grandmother is simply a path whose last clearing contains said house. For each clearing, its level of alternatives is the number of paths that go from it to RedCap's grandmother's house. In turn, for each path its level of alternatives is the sum of the levels of alternatives of all the clearings that make up that path. In order not to be captured by the wolf, RedCap wants to find the path with a maximum level of alternatives, starting at her house and ending at her grandmother's house. Can you help her?
Input
The first line contains two integer numbers N and S which respectively indicate the number of clearings and the number of pathways in the woods (3 ≤ N ≤ 3 × 10^{4} and 2 ≤ S ≤ 10^{5}). The clearings are identified by different integer numbers between 1 and N, and are ordered from west to east, so that if 1 ≤ i < j ≤ N then clearing i is to the west of clearing j. RedCap's house is in clearing 1, whereas her grandmother's house is in clearing N.
Each of the following S lines describes a pathway using two integer numbers I and J, which indicate that there is a pathway between clearing I and clearing J (1 ≤ I < J ≤ N). There is at least one path from RedCap's house to her grandmother's house, and the maximum level of alternatives among the set of all such paths is no greater than 10^{18}.
Output
Print a single line containing an integer number, representing the maximum level of alternatives for a path from RedCap's house to her grandmother's house.
Example 1
Input: 3 2 1 2 2 3 Output: 3
Example 2
Input: 4 6 1 2 2 3 3 4 1 2 2 3 3 4 Output: 15
Example 3
Input: 9 9 1 3 2 3 3 4 4 5 1 5 3 4 3 9 7 8 4 9 Output: 8
hide comments
sandeepd:
20200412 17:12:25
Nice problem, and not a bad explanation like a few others are complaining. In fact, one of the best worded problems here on spoj. 

nadstratosfer:
20190703 09:23:13
Enjoyable problem once you put the statement through search & replace in your favorite text editor. Use sys.setrecursionlimit(30000) to avoid NZEC when doing topdown in Python. 

whyamievenhere:
20190514 19:53:30
Extremely shitty explaination of the problem. 

Alaf Azam Khan:
20150722 02:52:54
Can someone please explain the given test cases. 

vikas:
20150523 07:41:17
If fails on 63rd case, maximum N is 30000 not 10000. 

Mitch Schwartz:
20140929 17:00:10
@Sachith: The judging does not stop on first failure; even if you see "Running... (62)", it's still possible that your code failed on the first data set. (And I see you've got AC now, so congrats :p .) 

Sachith:
20140929 17:00:10
WA on test case 63!!! o_O


Vinay Chandra Dommeti:
20140929 17:00:10
Can someone explain example 1? Should we include grandmother's house for counting the level of alternatives? 
Added by:  Fidel Schaposnik 
Date:  20131007 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Argentinian Programming Tournament 2013 