2015
09-17

# Sky

Little Qiang is watching the night sky after completing his math homework. After staring boringly at the sky for a while, he observes that actually many stars are lying on identical lines, so that a few number of parallel lines are suffice to cover all the stars in the sky. Being passionate about both astronomy and math, he decides to find out the minimum number of parallel lines to achieve the full coverage of stars. Moreover, the stars appear and disappear from time to time, making the problem more interesting.

Specifically, we assume that the stars are numbered from 1 to N. Initially, there are no stars in the sky. Then the sky will be refreshed for M rounds. For each round, one star will appear/disappear, and Little Qiang will compute again the result. Note that the same star could appear/disappear for more than once.

Unfortunately, Little Qiang has Trypophobia such that he cannot insist looking at the sky for a long period to finish the entire task. What a pity! Can you help him?

(The figure shows a concrete snapshot of the sky, where 3 parallel lines (the blue lines) are sufficed to cover all the 6 stars.)

There are multiple test cases. For each test case, there will be two integers N (1<=N<=500) and M (1<=M<=1000) in the first line as stated above. Each of the following N lines has two integers x and y (-1000000 < x, y < 1000000), indicating the coordinates of each star (from 1 to N). Then M lines follows, representing M rounds of refreshes of the sky. Each of the M lines has two integers a and b, where a = 0/1 means that b-th (1<=b<=N) star appears/disappears in the sky. Your program should proceed to the end of file.

You can assume that an appeared star would not appear again before its next disappearance, and a disappeared star would not disappear again before its next appearance.

There are multiple test cases. For each test case, there will be two integers N (1<=N<=500) and M (1<=M<=1000) in the first line as stated above. Each of the following N lines has two integers x and y (-1000000 < x, y < 1000000), indicating the coordinates of each star (from 1 to N). Then M lines follows, representing M rounds of refreshes of the sky. Each of the M lines has two integers a and b, where a = 0/1 means that b-th (1<=b<=N) star appears/disappears in the sky. Your program should proceed to the end of file.

You can assume that an appeared star would not appear again before its next disappearance, and a disappeared star would not disappear again before its next appearance.

4 6
0 0
0 1
0 2
1 1
0 1
0 3
0 2
0 4
1 2
1 1

1
1
1
2
2
1


1. ***月开始就说急性肺炎，到现在仙逝一直在住院，这样的急性肺炎也是醉了。再看从年初就一直反复发烧，有这样的急性病么。***成是一直抱恙但为了工作在***月之前一直撑着瞒着。

2. 常在东亚服混（国人最多），排位不知道，休闲局高调挂很少碰到，低调挂演技高看不出来。不过最近反作弊系统发威，倒是封掉了不少大神。

3. 常在东亚服混（国人最多），排位不知道，休闲局高调挂很少碰到，低调挂演技高看不出来。不过最近反作弊系统发威，倒是封掉了不少大神。

4. 常在东亚服混（国人最多），排位不知道，休闲局高调挂很少碰到，低调挂演技高看不出来。不过最近反作弊系统发威，倒是封掉了不少大神。