Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

MNERED - NERED

Đọc đề đẹp hơn ở:
https://codeforces.com/group/FLVn1Sc504/contest/274710/problem/W
https://codeforces.com/group/FLVn1Sc504/contest/274506/problem/W

{assign var="code" value="MNERED"} {if $par==""} {assign var=par value=$locale} {/if}

{if $par=="vn"} {literal}

 

Cho hình vuông NxN, một số ô có các hộp, mỗi ô có thể có nhiều hộp bao nhau. Tính số hộp cần chuyển ít nhất để các hộp này xếp thành 1 hình chữ nhật (mỗi ô chỉ có 1 hộp). Phép chuyển hộp là chuyển 1 hộp ở trên cùng ở một ô vuông sang và đặt ở trên cùng 1 ô vuông nào khác.

 

Input

 

DÒng đầu là 2 số N và M, (1 ≤ N ≤ 100, 1 ≤ M ≤ N^2), kích thước hình vuông và số hộp. M dòng tiếp theo là tọa độ mỗi hộp (hàng, cột).

 

Output

 

Số hộp ít nhất cần chuyển

 

Sample

input
4 3
2 2
4 4
1 1
output
2

input
5 8
2 2
3 2
4 2
2 4
3 4
4 4
2 3
2 3
output
3

Ở ví dụ 2, hộp chuyển từ (2, 3) tới (3, 3), từ (4, 2)
tới (2, 5) và từ (4, 4) tới (3, 5).

{/literal} {elseif ($par=="en" || $par=="")}{literal}

 

In the nearby kindergarten they recently made up an attractive game of strength and agility that kids love. The surface for the game is a large flat area divided into N×N squares. The children lay large spongy cues onto the surface. The sides of the cubes are the same length as the sides of the squares. When a cube is put on the surface, its sides are aligned with some square. A cube may be put on another cube too. Kids enjoy building forts and hiding them, but they always leave behind a huge mess. Because of this, prior to closing the kindergarten, the teachers rearrange all the cubes so that they occupy a rectangle on the surface, with exactly one cube on every square in the rectangle. In one moving, a cube is taken off the top of a square to the top of any other square.

Write a program that, given the state of the surface, calculates the smallest number of moves needed to arrange all cubes into a rectangle.

 

Input

 

The first line contains the integers N and M (1 ≤ N ≤ 100, 1 ≤ M ≤ N^2), the dimensions of the surface and the number of cubes currently on the surface.

Each of the following M lines contains two integers R and C (1 ≤ R, C ≤ N), the coordinates of the square that contains the cube.

 

Output

 

Output the smallest number of moves. A solution will always exist.

 

Sample

input
4 3
2 2
4 4
1 1
output
2

input
5 8
2 2
3 2
4 2
2 4
3 4
4 4
2 3
2 3
output
3

In the second example, a cube is moved from (2, 3) to (3, 3), from (4, 2)
to (2, 5) and from (4, 4) to (3, 5).

{/literal} {/if}


Được gửi lên bởi:~!(*(@*!@^&
Ngày:2009-03-08
Thời gian chạy: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:COCI 6th 09

hide comments
2017-10-05 03:36:34
Trau cung ac
2017-09-20 16:08:04
Đề này có thể có những trường hợp không chuyển được không? Chẳng hạn có 3 hộp mà N lại bằng 2.
Lúc này hình chữ nhật chỉ có thể xếp là 1x3 hay 3x1 không thể xếp được.
2017-09-12 13:18:25
Trâu = AC :3
2014-09-23 14:24:38 Thần Ðồng Mẫu Giáo
bài gì mà không có giới hạn :3
2014-08-18 13:58:13 Bùi Hữu Giáp
Toàn sai Test thứ 10 mới chết chứ!
2013-11-12 17:01:43 In God We Trust
sai test cuối vãi
2013-06-14 14:21:10 Bitagi97
bài này làm khó chịu quá đi

Last edit: 2013-07-10 04:10:51
2013-06-12 15:45:03 a;slkfjasl;fkj
làm thế nào ta?
2013-05-27 18:03:20 ‡■■Lãng du■■‡
::::==== Anh Voyage
Sao hinh vuông 2x2 lại có ô 1 3
2012-08-03 02:58:13 KAKALOT
?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.