CARDSHUF  Cards shuffing
English  Tiếng Việt 
"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 i^{th} card then put it on the j^{th} of the remaining cards (1 ≤ i, j ≤ n). If j = n, the i^{th} 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 p^{th} line contains two integer i_{p}, j_{p} describing the p^{th} time of shuffing (S(i_{p}, j_{p})).
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 ≤ 10^{5}.
hide comments
treenipples:
20211103 11:14:44
Treap + Segment tree passes 

Stupid Dog:
20150221 04:32:37
FastIO + rb_tree_tag = time limit exceeded 

Danh Nguyen:
20130815 23:42:43
@Buda IM: Could you please provide your Faster IO methods? 

Buda IM (retired):
20120507 19:37:17
Faster IO methods should be used, my N log N passes only with fast io 

Seshadri R:
20111118 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:
20091029 08:45:36
Under Limitations, it is stated that

Added by:  AnhDQ 
Date:  20090519 
Time limit:  0.100s1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  Mr Hoang Le Minh (HNEU)  Vietnam 