Network Vulnerability

Network vulnerability describes how much network performance drops under disruptions such as natural disasters, element failures, or adversarial attacks. A network is often modeled as a graph, where vertices correspond to nodes and edges to links, so the two terms network and graph are used interchangeably. The connectivity is the minimum number of vertices whose deletion leaves a disconnected graph or a one-vertex graph. It is the most important measure of network vulnerability.

Connectivity captures only part of a graph's resistance to vertex deletion. Many other metrics have been proposed, and the toughness and the scattering number are the most popular. Both rest on the maximum number of connected components left after removing k vertices. Let $c_k(G)$ denote the maximum number of connected components obtained by removing exactly $k$ vertices from a graph $G$. Given a graph $G$ and a positive integer $k$, computing $c_k(G)$ is computationally intractable.

For some graph classes, such as interval graphs, $c_k(G)$ can be computed in polynomial time. An interval graph is the intersection graph of a family of (closed) intervals on the real line. Two vertices are joined by an edge if and only if their intervals intersect. The family is called an interval representation of the graph. The figure shows an interval graph and its interval representation.

(a) an interval graph	(b) an interval representation of the graph of (a)

Given an interval representation of an interval graph $G$ with $n$ vertices, write an efficient program that computes $c_k(G)$ for all $k \in \{0, 1, \ldots, n-1\}$. For the representation in figure (b), $c_0(G), c_1(G), \ldots, c_7(G)$ are 1, 1, 1, 2, 2, 3, 2, 1, respectively.

The first line contains a positive integer $n$, the number of intervals, where $n \le 2{,}000$. Each of the next $n$ lines contains the left and right endpoints of one interval. All endpoints are integers between $-100{,}000{,}000$ and $100{,}000{,}000$, inclusive.

Print one line with $n$ numbers $c_0(G), c_1(G), \ldots, c_{n-1}(G)$, separated by single spaces.