CARDSHUF - Cards shuffing

"Phú ông" has a card deck consits of n cards. He writes on each card a number from 1 to n from the top to the bottom of the deck.
Then he does shuffle the card deck several times, each time is described by S(i, j) meaning: pull out the ith card then put it on the jth of the remaining cards (1 ≤ i, j ≤ n). If j = n, the ith card will be the bottom card of the new one.
For example (n=6):

Afer x times of shuffing, "Phú ông" gives "Bờm" the card deck and chanllenges him to make it into the original order. Please help "Bờm"!

Input

- The first line contains two integer n, x.
- Next x line(s), the pth line contains two integer ip, jp describing the pth time of shuffing (S(ip, jp)).

Output

- A single integer means the minimal number of times of shuffing the card deck to help "Bờm".

Example

Input:
6 4
2 3
1 2
4 5
1 6

Output:
2

Limitations

- 1 ≤ n, x ≤ 105.


Added by:AnhDQ
Date:2009-05-19
Time limit:0.100s-1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:Mr Hoang Le Minh (HNEU) - Vietnam

hide comments
2021-11-03 11:14:44
Treap + Segment tree passes
2015-02-21 04:32:37 Stupid Dog
FastIO + rb_tree_tag = time limit exceeded
2013-08-15 23:42:43 Danh Nguyen
@Buda IM: Could you please provide your Faster IO methods?
2012-05-07 19:37:17 Buda IM (retired)
Faster IO methods should be used, my N log N passes only with fast io
2011-11-18 09:53:34 Seshadri R
One more example with i and j differing by more than one would have helped. Otherwise, except for the last one, all the illustrations mislead the reader to think that it is a simple exchange of i and j.
2009-10-29 08:45:36 Seshadri R
Under Limitations, it is stated that
- 1 ≤ n, x ≤ 10 to the power of 5.
Is the minus sign in front of 1 a typo?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.