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.


Được gửi lên bởi:AnhDQ
Ngày:2009-05-19
Thời gian chạy:0.100s-1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:Mr Hoang Le Minh (HNEU) - Vietnam

hide comments
2021-05-27 18:00:26
Tham khảo: https://vnspoj.github.io/problems/CARDSHUF
2020-04-20 08:22:49


Last edit: 2020-04-20 08:47:51
2016-11-03 14:54:19
Code pascal:
http://shink.in/4rng8
2015-11-03 23:15:01
Tham khảo : http://www.oni.vn/uR57W

Blog Thuật toán SPOJ (vnspoj) hy vọng giúp mọi người với solution và code hơn 300 bài tại : http://www.oni.vn/uR57W
2015-08-16 07:01:59 [Nghien] Le Long
undo ???
2014-11-01 23:56:19 Nguyễn Duy Long
splay tree
2011-01-25 14:26:35 Hy Trường Sơn
nice problem!
2010-03-05 15:25:45 phoebe
sao time bài này chặt thế +_+'!!!!!!:((
2009-07-02 07:21:16 Mệt
- chắc là gạch đầu dòng thôi.
2009-07-01 16:43:33
-1 <= n, x <= 10^5.
Nếu n = -1 thì kq thế nào nhỉ.

Bài này của thầy Hoàng, HNUE (tự nhiên AnhDQ móc đâu ra HNEU +_@)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.