{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"\n \u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003e\n Bessie 驾驶着他的太空飞船呆呆2号在太空旅行,途径一段危险地带,他希望自己能安全通过这段区域,于是他将这片区域的地图扫描进入了太空飞船,地图是一个N x N的网络 (1 \u0026lt;\u003d N \u0026lt;\u003d 500),其中有K颗小行星 (1 \u0026lt;\u003d K \u0026lt;\u003d 10,000)。\n \u003cbr\u003e \n \u003cbr\u003e还好Bessie有一个强力的武器能够一发光束将一整行或者一整列的小行星轰成灰烬。 这种光束的价格高昂,材料稀有,所以他希望更少的使用这个光束。现在把地图给你,你能帮Bessie计算一下,摧毁掉这些小行星至少需要几发光束。\n \u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\n \u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003e\n * Line 1: 两个整数N和K,中间用空格隔开。 \n \u003cbr\u003e* Lines 2..K+1: 每一行有两个整数R和C (1 \u0026lt;\u003d R, C \u0026lt;\u003d N) ,代表行和列,即小行星i的位置是(Ri,Ci)。\n \u003c/div\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\n \u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003e\n * Line 1: 输出一个整数表示最少需要几发光束。\n \u003c/div\u003e"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cpre class\u003d\"sio\"\u003e3 4\n1 1\n1 3\n2 2\n3 2\n\u003c/pre\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cpre class\u003d\"sio\"\u003e2\n\u003c/pre\u003e"}},{"title":"Hint","value":{"format":"HTML","content":"\n \u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003e\n 输入解释: \n \u003cbr\u003e上述的输入样例如图所示(\"X\"代表小行星,\".\"代表安全地带): \n \u003cbr\u003e\n \u003ctt\u003eX.X \u003cbr\u003e.X. \u003cbr\u003e.X.\u003c/tt\u003e \n \u003cbr\u003e \n \u003cbr\u003e输出解释:\n \u003cbr\u003eBessie发射第一发光束毁掉(1,1)和(1,3)两处小行星, 然后发射第二发光束毁掉(2,2)和(3,2)两处小行星。\n \u003c/div\u003e"}}]}