You are listening to an interesting lecture about 1-String B2-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
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
The next
The next
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
Comments
This comment is hidden due to too much negative feedback. Show it anyway.
That's just unfortunate.
https://redmond.life/pages/realsalt
I think he's already had his sodium intake for the day.