Exactly One Point

면접 대비

시간 제한2초메모리 제한512 MB

요약

n개의 선분이 주어질 때, 각 선분이 정확히 한 점을 포함하고 모든 점이 어떤 선분에 속하도록 서로 다른 점을 배치하거나 불가능함을 판별한다.

문제

There are $n$ segments on a line. You should place some points onto this line so that:

The first line contains an integer $n$ ( $1 \le n \le 200000$ ) --- the number of segments.

Each of the next $n$ lines contains two integers $L\_i$ and $R\_i$ ( $L\_i < R\_i$ ) --- the endpoints of the $i$ -th segment.

For convenience, all endpoints of all segments are even numbers from $0$ to $4n - 2$ .

If it's impossible to place points in a required way, output "-1".

Otherwise, in the first line output an integer $m$ --- the number of points that should be placed onto the line.

In the next line, output $m$ distinct integers from $0$ to $4n - 2$ --- the coordinates of the points.

You don't have to minimize the number of points. If there are several possible solutions, output any of them.