P3229 [HNOI2013] Travel

In the distant country of HX, there lives a traveler named Xiao L. He wants to ride his bicycle across the entire country. There are $n$ cities in this country, numbered from $1$ to $n$. Some cities have no attraction that Xiao L wants to visit, while some cities have exactly one such attraction. Every city is one of these two types. As an information science enthusiast, he wrote a program that arranged a shortest route to reach all the attractions he wants to visit (the city numbers along the route are in an arbitrary order). He reaches city $a_1$ first, city $a_i$ as the $i$-th city, and finally ends the trip at city $a_n$. Xiao L wants to finish this trip in exactly $m$ months ($m < n$), so he needs a sensible plan. When he arrives at a city, if that city has an attraction he wants to visit, he gains $1$ point of happiness; otherwise, he gains $1$ point of fatigue due to the tiring journey. One month is enough for him to travel through any number of cities, but he also wants to take some time to rest. He always rests in the last city he reaches in that month (if this city has an attraction, Xiao L will always visit the attraction before resting). Of course, Xiao L wants to have some travel tasks every month. Even if none of the cities he reaches that month has an attraction, he will still arrive at least one new city in that month. Xiao L cannot arrange the travel plan by himself, so he asks for your help. You need to provide a sequence $x_1, x_2, \ldots, x_m$, where $x_i$ is the city number where Xiao L rests in the $i$-th month. Since he must finish his trip in the last month, $x_m$ must equal $a_n$. For example, let $n = 5$, $m = 3$, $(a_1, a_2, a_3, a_4, a_5) = (3, 2, 4, 1, 5)$, and $(x_1, x_2, x_3) = (2, 1, 5)$. This means: in month $1$ he reaches cities $3$ and $2$ in order and rests in city $2$; in month $2$ he reaches cities $4$ and $1$ in order and rests in city $1$; in month $3$ he reaches city $5$ and rests in city $5$. There are many such feasible sequences. Let $d_i$ be the absolute value of the difference between the happiness and fatigue obtained in month $i$ for a given plan. For the $k$-th feasible plan, let $c_k$ be the maximum of $d_1, d_2, \ldots, d_m$. Xiao L wants to choose a plan that minimizes $c_k$ among all feasible plans. In fact, there may be multiple plans achieving the same minimal $c_k$. Since Xiao L loves programming, he has a bit of OCD (and believes that it makes him look cool). Among all the plans with minimal $c_k$, he wants the lexicographically smallest sequence. Tips: To compare two sequences lexicographically, compare the first position where they differ, e.g., $(1, 2, 3, 4) < (1, 2, 4, 3)$.

The first line contains two space-separated positive integers $n, m$, denoting the number of cities and the number of months. The next $n$ lines each contain two space-separated integers $A_i$ and $B_i$. Here $A_i$ is the city number he reaches in the $i$-th step, and $B_i$ is $0$ or $1$. If $B_i = 0$, then city $A_i$ has no attraction Xiao L wants to visit; if $B_i = 1$, then city $A_i$ has such an attraction. The $A_i$ are pairwise distinct and satisfy $1 \leq A_i \leq n$, i.e., $\{A_i\}$ is a permutation of $1, 2, \ldots, n$.

Output exactly one line containing $m$ space-separated positive integers $X_1, X_2, \ldots, X_m$, which is the planned sequence of rest-city numbers for Xiao L’s trip.

In the first month, he gains $2$ points of happiness and $2$ points of fatigue. In the second month, he gains $1$ point of happiness and $1$ point of fatigue. In the third month, he gains $1$ point of happiness and $1$ point of fatigue. The maximum difference between fatigue and happiness over the $3$ months is $0$, which is the minimal possible value among all plans. Feasible plans include: - 1 6 8 - 3 6 8 - 3 1 8 Among these, 1 6 8 is lexicographically smallest. Constraints: $n \leq 5 \times 10^5$, $m \leq 2 \times 10^5$. Translated by ChatGPT 5