TopCoder

User's AC Ratio

87.5% (7/8)

Submission's AC Ratio

73.3% (11/15)

Tags

Description

李胖在看天外奇蹟。
他注意到天上掉下來了很多石頭,落在了李胖家的院子裡。
李胖是數學高手,所以他將石頭依位置標示,形式如$(x_i,y_i)$。
李胖討厭石頭,所以他要摧毀他們,他的絕招是Laplace,一次可以清除一直行或一橫列的石頭。
可是使用Laplace會耗費李胖大量的能量,讓他想吃東西,使得他減肥失敗。
所以李胖想要使用盡量少的Laplace,把院子裡的石頭清光,你可以告訴他最少要用幾次Laplace嗎?

Input Format

輸入第一行包含兩個整數$N,K$,代表李胖院子的大小($N\times N$)以及石頭的數量。
接著$K$行每行包含兩個整數$x_i,y_i(1\le x_i,y_i\le N)$,分別代表第$i$顆石頭在李胖院子上的座標位置。

Output Format

輸出李胖最少需要用幾次Laplace,才能將石頭清除?

Sample Input

3 4
1 1
1 3
2 2
3 2

Sample Output

2

Hints

For $20\%$ of the testdata: $N\le 10,K\le 100$.
For $50\%$ of the testdata: $N\le 100,K\le 1000$.
For $100\%$ of the testdata: $N\le 500,K\le 10000$.

Problem Source

Subtasks

For Testdata: 0 ~ 3, Score: 20
For Testdata: 4 ~ 7, Score: 30
For Testdata: 8 ~ 11, Score: 50
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 65536 65536
1 1000 65536 65536
2 1000 65536 65536
3 1000 65536 65536
4 1000 65536 65536
5 1000 65536 65536
6 1000 65536 65536
7 1000 65536 65536
8 1000 65536 65536
9 1000 65536 65536
10 1000 65536 65536
11 1000 65536 65536