You are listening to an interesting lecture about *1-String B _{2}-VPG Representation of Planar Graphs* given by M. Derka, but as the presentation goes on and your understanding of the lecture lessens, your thoughts wander off into the realm of planar graphs…

You dream of a glorious planar graph. You wonder: what is the size of the *maximum clique* in this graph? A *clique* is a subgraph of the graph such that each pair of vertices in the clique are connected to each other by an edge. Specifically, a set of one single vertex is considered a clique. A *maximum clique* is a clique that has the most vertices out of all cliques in a graph.

Since you are skeptical that your graph is actually planar, you are determined to remove some edges such that it becomes planar. Therefore, your procedure of making the graph is as follows: first, you draw points on the Cartesian plane. These will be your vertices, numbered from to . Then, you consider straight-line edges between the points in order. If adding an edge would make the graph non-planar (i.e. it intersects a previously added edge somewhere which is not the endpoints of the edge), you discard it. In particular, two lines that have infinitely many common points do intersect. Otherwise, you add it to the graph.

After making your graph in this fashion, you are too exhausted to complete your original goal by hand. Therefore, you decide to redo the whole procedure, but this time with a program you are about to write.

#### Input Specification

The first line of input will have two integers and .

The next lines will have integer and pairs , the coordinates of each vertex in the graph in order from vertex to vertex . No two points will be at the same location. **Additionally, no three points will be collinear**.

The next lines will have and pairs , indicating that you should consider adding an edge from to .

#### Constraints

##### Subtask 1 [30%]

##### Subtask 2 [20%]

##### Subtask 3 [50%]

#### Output Specification

You should output the size of the maximum clique on one line.

#### Sample Input

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

#### Sample Output

`3`

#### Explanation of Output for Sample Input

The graph is a square, but the last edge isn't in the graph as its presence would make the given embedding of the graph non-planar. There are two maximum cliques of size , and .

## Comments

*Is the subtask weight assigned correctly? I mean 50% for n <= 20 and just 30% for n <= 300 ?

Fixed, thanks for noticing. I've updated the problem statement.

This comment is hidden due to too much negative feedback. Click here to view it.

That's just unfortunate.

http://www.realsalt.com/

I think he's already had his sodium intake for the day.

Does segments intersect if they has infinitely many common points?

Sorry, consider that they

DOintersect. I will verify the test data again.Please reply when you'll finish this check

I am really sorry. I will remove all cases with 3 collinear points. The reason is because that no matter which way of interpreting this scenario, the result is not good.

Can we assume no three points are collinear?

You can assume that now.