This is a different version of problem A. 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 do not 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);
}