CARDSHUF - Cards shuffing

no tags 

"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.


hide comments
treenipples: 2021-11-03 11:14:44

Treap + Segment tree passes

Stupid Dog: 2015-02-21 04:32:37

FastIO + rb_tree_tag = time limit exceeded

Danh Nguyen: 2013-08-15 23:42:43

@Buda IM: Could you please provide your Faster IO methods?

Buda IM (retired): 2012-05-07 19:37:17

Faster IO methods should be used, my N log N passes only with fast io

Seshadri R: 2011-11-18 09:53:34

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.

Seshadri R: 2009-10-29 08:45:36

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?


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