TAP2013C - Little Red-Cap

[The original version of this problem (in Spanish) can be found at http://www.dc.uba.ar/events/icpc/download/problems/tap2013-problems.pdf]

Once upon a time there was a very joyous girl who was called Little Red-Cap because she always wore a red riding cap. Red-Cap 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, Red-Cap definitely did not enjoy the perils of the woods, and in particular the Big Bad Wolf who was always hungry and prying.

One day, Red-Cap 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. Red-Cap'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 Red-Cap knows very well. In order not to get lost, Red-Cap 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 Red-Cap 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 Red-Cap'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 Red-Cap'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, Red-Cap 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?



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 × 104 and  S  105). The clearings are identified by different integer numbers between 1 and N, and are ordered from west to east, so that if  i < j  N then clearing i is to the west of clearing j. Red-Cap'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 ( I < J  N). There is at least one path from Red-Cap's house to her grandmother's house, and the maximum level of alternatives among the set of all such paths is no greater than 1018.



Print a single line containing an integer number, representing the maximum level of alternatives for a path from Red-Cap's house to her grandmother's house.


Example 1

3 2
1 2
2 3


Example 2

4 6
1 2
2 3
3 4
1 2
2 3
3 4


Example 3

9 9
1 3
2 3
3 4
4 5
1 5
3 4
3 9
7 8
4 9


hide comments
sandeepd: 2020-04-12 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: 2019-07-03 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 top-down in Python.

whyamievenhere: 2019-05-14 19:53:30

Extremely shitty explaination of the problem.

Alaf Azam Khan: 2015-07-22 02:52:54

Can someone please explain the given test cases.

vikas: 2015-05-23 07:41:17

If fails on 63rd case, maximum N is 30000 not 10000.

Mitch Schwartz: 2014-09-29 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: 2014-09-29 17:00:10

WA on test case 63!!! o_O

Vinay Chandra Dommeti: 2014-09-29 17:00:10

Can someone explain example 1? Should we include grandmother's house for counting the level of alternatives?

Added by:Fidel Schaposnik
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Argentinian Programming Tournament 2013