CARDSHUF - Cards shuffing

Phú ông có bộ bài gồm n lá bài. Phú ông xếp chúng thành tập và ghi vào mỗi lá bài số thứ tự ban đầu của lá bài đó trong tập bài (vị trí các lá bài được đánh số từ 1 tới n từ trên xuống dưới).
Tiếp theo Phú ông tiến hành tráo tập bài, mỗi phép tráo kí hiệu bởi S(i, j): rút ra lá bài thứ i và chèn lên trên lá bài thứ j trong số n - 1 lá bài còn lại (1 ≤ i, j ≤ n), quy ước rằng nếu j = n thì lá bài thứ i sẽ được đặt vào vị trí cuối cùng của tập bài.
Ví dụ (n=6):

Sau x phép tráo bài, Phú ông đưa cho Bờm tập bài và thách Bờm dùng ít phép tráo nhất để xếp lại các lá bài về vị trí ban đầu. Hãy giúp Bờm thực hiện điều đó.

Dữ liệu

- Dòng đầu tiên chứa hai số nguyên dương n, x.
- x dòng tiếp theo, dòng thứ p chứa hai số nguyên ip, jp cho biết phép tráo thứ p của Phú ông là S(ip, jp).

Kết quả

- Một số duy nhất là số phép tráo cần thực hiện để đưa các lá bài về vị trí ban đầu.

Ví dụ

Dữ liệu:
6 4
2 3
1 2
4 5
1 6

Kết quả:
2

Giới hạn

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