No Collision Moves

AtCoder

IDarc205_c

Time3000ms

Memory256MB

Difficulty—

There are $N$ people on a number line. Person $i$ $(1\le i\le N)$ is initially at coordinate $S_i$, and wants to eventually move to coordinate $T_i$. It is guaranteed that $S_1,S_2,\ldots,S_N,T_1,T_2,\ldots,T_N$ are all distinct. You fix one permutation $P=(P_1,P_2,\ldots,P_N)$ of $(1,2,\ldots,N)$ and perform $N$ operations in order. In the $i$\-th operation $(1\le i\le N)$, you move person $P_i$ from coordinate $S_{P_i}$ to coordinate $T_{P_i}$ along the shortest path on the number line. However, if there is another person on the movement path, a fight occurs. Determine if there exists a $P$ such that no fight occurs, and if it exists, find one. ## Constraints * $1\le N\le 2\times 10^5$ * $1\le S_i, T_i \le 10^9$ * $S_1,S_2,\ldots,S_N,T_1,T_2,\ldots,T_N$ are all distinct. * All input values are integers. ## Input The input is given from Standard Input in the following format: $N$ $S_1$ $T_1$ $S_2$ $T_2$ $\vdots$ $S_N$ $T_N$ [samples]

Samples

Input #1

Output #1

Yes
3 2 1 4

If $P=(3,2,1,4)$, then the $N$ operations proceed as follows.

*   $1$st operation: Move person $3$ from coordinate $7$ to coordinate $5$. The other three people are at coordinates $1,2,8$, so no fight occurs.
*   $2$nd operation: Move person $2$ from coordinate $2$ to coordinate $4$. The other three people are at coordinates $1,5,8$, so no fight occurs.
*   $3$rd operation: Move person $1$ from coordinate $1$ to coordinate $3$. The other three people are at coordinates $4,5,8$, so no fight occurs.
*   $4$th operation: Move person $4$ from coordinate $8$ to coordinate $10$. The other three people are at coordinates $3,4,5$, so no fight occurs.

Therefore, outputting $P=(3,2,1,4)$ will be accepted.
Other acceptable outputs include $P=(4,3,2,1),(2,1,3,4)$.

Input #2

2
1 3
4 2

Output #2

No

There is no $P$ such that no fight occurs. Therefore, output `No`.

Input #3

Output #3

Yes
3 5 1 4 2

API Response (JSON)

{
  "problem": {
    "name": "No Collision Moves",
    "description": {
      "content": "There are $N$ people on a number line. Person $i$ $(1\\le i\\le N)$ is initially at coordinate $S_i$, and wants to eventually move to coordinate $T_i$. It is guaranteed that $S_1,S_2,\\ldots,S_N,T_1,T_2,",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "arc205_c"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "There are $N$ people on a number line.\nPerson $i$ $(1\\le i\\le N)$ is initially at coordinate $S_i$, and wants to eventually move to coordinate $T_i$. It is guaranteed that $S_1,S_2,\\ldots,S_N,T_1,T_2,...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments