Bessie and Elsie have each baked \(N\) pies (\(1 \leq N \leq 10^5\)). Each of the
\(2N\) pies has a tastiness value according to Bessie and a (possibly different)
tastiness value according to Elsie.

Bessie is thinking about giving one of her pies to Elsie. If Elsie receives a
pie from Bessie, she will feel obligated to give one of her pies to Bessie. So
as to not appear stingy nor flamboyant, Elsie will try to pick a pie that is at
least as tasty (in Elsie's eyes) as the pie she received, but no more than \(D\)
units tastier (\(0 \leq D \leq 10^9\)). Such a pie may not exist, in which case
Elsie will adopt a pseudonym and exile herself to Japan.

But if Elsie does give Bessie a pie in return, Bessie will similarly try to give
Elsie a pie which is at least as tasty but no more than \(D\) units tastier (in
Bessie's eyes) as the pie Elsie just gave her. Should this be impossible, Bessie
too will exile herself. Otherwise she will give her chosen pie to Elsie. This
cycle will continue until one of the cows is exiled, an unhappy outcome, or one
of the cows receives a pie which she accords a tastiness value of \(0\), in which
case the gift exchange will end and both cows will be happy.

Note that a pie may not be gifted twice, nor can either cow return a pie gifted
to her.

For each of the \(N\) pies Bessie could select as her initial gift to Elsie, determine the
minimum number of pies that could possibly be gifted in the resulting exchange
before the cows are happy.

Problem credits: Dhruv Rohatgi

Problem credits: Dhruv Rohatgi

The first line contains the two integers \(N\) and \(D\).

The next \(2N\) lines contain two space-separated integers each, respectively
denoting the value of a particular pie according to Bessie, and the value of
that pie according to Elsie.

The first \(N\) lines refer to Bessie's pies, and the remaining \(N\) lines refer to
Elsie's pies.

It is guaranteed that all tastiness values are in the range \([0,10^9]\).

There should be \(N\) lines in the output. Line \(i\) should contain a single
integer: the minimum number of pies that could be gifted in a happy gift
exchange started with Bessie's pie \(i\). If no gift exchange starting with pie
\(i\) is happy, then line \(i\) should contain the single integer \(-1\) instead.

riseoj 작성

출처 올림피아드 > USACO > 2017-2018 > December > Gold