### 2007 Canadian Computing Competition, Stage 1

## Problem S4: Waterpark

The local waterpark has a great slide complex, with many paths crisscrossing down the hill. There is one start point and one end point, but at various points one can turn and take different paths. Walter and Wanda are wondering exactly how many different ways there are to go down the slide. Can you solve their problem?

More precisely, there are `n` marked points (including the start at 1 and the end at `n`) where the paths down the hill may split or merge. All paths move down the hill to higher numbered positions; some paths will actually cross over others without meeting but we don’t have to worry about that. We won’t worry about the collisions between sliders that can happen either. Our problem is simply to determine the number of different sequences of marked points we can follow down the hill.

For example, at one small waterpark, there are 4 points with direct slides from 1 to points 2 and 4; from 2 to 3 and 4; and from 3 to 4. There are 3 ways down the hill. You can check this by seeing that we can go (1,2,3,4), (1,2,4) or (1,4).

(Here is a hint: think about starting at the bottom of the slide.)

### Input

Input begins with a single integer `n` (1 ≤` n` ≤ 9999), on a line by itself, indicating the number of marked points. The next lines contain point pairs of the of the form `x` `y`, where 1 ≤` x` < `y` ≤` n`. For example, 1234 8765 indicates a direct slide from point 1234 to point 8765. The last line of input will be indicated by point pair 0 0.

### Output

The output is an integer, which is the number of different paths from point 1 to point `n`. You can assume that the number of paths will be less than 2^{30}. It is possible that there is no path from point 1 to point `n`, in which case the number of paths is 0.

### Sample Input

`4`

1 2

1 4

2 3

2 4

3 4

0 0

### Sample Output

`3`

All Submissions

Best Solutions

**Point Value:** 10

**Time Limit:** 2.00s

**Memory Limit:** 16M

**Added:** Sep 30, 2008

**Problem Types:**[Show]

**Languages Allowed:**

C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

## Comments (Search)

4Dmovieon Apr 12, 2016 - 8:16:12 pm UTC Re at the 4th test casetot++;

edge[tot].from = x, edge[tot].to = y;

I don't know what's wrong. Anyone can help me?

Thanks!

jimgaoon Feb 09, 2016 - 11:51:37 pm UTC Hint?jargonon Feb 11, 2016 - 2:49:26 am UTC Re: Hint?jungernaut165on Apr 21, 2015 - 7:38:10 am UTCfifimanon Apr 21, 2015 - 7:49:53 pm UTC Re: ...jungernaut165on Apr 21, 2015 - 9:22:45 pm UTC Re: ...thorthugnastyon Apr 21, 2015 - 10:16:17 pm UTC Re: ...jungernaut165on Apr 22, 2015 - 4:25:11 am UTC Re: ...jungernaut165on Apr 21, 2015 - 5:42:52 am UTCBingon Mar 18, 2015 - 1:52:20 am UTC Segmentation Fault?fifimanon Mar 18, 2015 - 1:56:35 am UTC Re: Segmentation Fault?andrewkweonon May 21, 2014 - 4:02:59 pm UTC invalid return?fifimanon May 22, 2014 - 12:19:19 am UTC It might be thisSourSpinachon Apr 23, 2012 - 6:15:33 pm UTC ClarificationSourSpinachon Feb 11, 2011 - 1:49:54 am UTC ClarificationDanielon Jan 17, 2009 - 1:53:31 pm UTC Can I get 30 points now for this?hansonw1on Jan 17, 2009 - 2:31:02 pm UTC Re: Can I get 30 points now for this?Danielon May 06, 2009 - 8:23:36 pm UTC Re: Re: Can I get 30 points now for this?now can i get 30 pts?

Bobon Jan 28, 2009 - 3:04:22 am UTC Can someone help debug my program?(I don't really understand how to indent a program!!!)

ultblad1on Jan 28, 2009 - 10:44:56 pm UTC Re: Can someone help debug my program?Asking makes you a fool for a minute, not asking makes you a fool for a lifetime.