This is a different version of problem B. The only difference between the two versions is the validity condition for a coloring.

After competing virtually in all CodeForces rounds of the past three years, Geosé finally mastered graph problems. Graph coloring became his favorite topic in graph theory. While looking for a problem that combines this topic and geometry, he came up with the following problem:

You are given a convex polygon with $$$n$$$ vertices. For each pair of vertices, a line segment connecting them is drawn. Note that $$$\binom{n}{2}$$$ segments are drawn in total.

You must assign a color to each segment. A coloring is said to be valid if it satisfies the following condition:

• If two segments intersect, they must have different colors.

Two segments are considered to intersect if they share at least one common point, including endpoints. In particular, segments that share a vertex are also considered intersecting.

Determine the minimum number of colors required to obtain a valid coloring.

Note: since the input and output are large, you may need to optimize them for this problem.

For example, in C++, it is enough to use the following lines at the start of the main() function:

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr); std::cout.tie(nullptr);
}