시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 128 MB | 1 | 1 | 1 | 100.000% |
There is a famous joke-riddle for children:
Three turtles are crawling along a road. One turtle says: "There are two turtles ahead of me." The other turtle says: "There are two turtles behind me." The third turtle says: "There are two turtles ahead of me and two turtles behind me." How could this have happened?
The answer is --- the third turtle is lying!
Now in this problem you have $n$ turtles crawling along a road. Some of them are crawling in a group, so that they do not see members of their group neither ahead nor behind them. Each turtle makes a statement of the form: "There are $a_i$ turtles crawling ahead of me and $b_i$ turtles crawling behind me." Your task is to find the minimal number of turtles that must be lying.
Let us formalize this task. Turtle $i$ has $x_i$ coordinate. Some turtles may have the same coordinate. Turtle $i$ tells the truth if and only if $a_i$ is the number of turtles such that $x_j>x_i$ and $b_i$ is the number of turtles such that $x_j<x_i$. Otherwise, turtle $i$ is lying.
The first line of the input file contains integer number $n$ ($1 \le n \le 1000$). It is followed by $n$ lines containing numbers $a_i$ and $b_i$ ($0 \le a_i, b_i \le 1000$) that describe statements of each turtle for $i$ from 1 to $n$.
On the first line of the output file write an integer number $m$ --- the minimal number of turtles that must be lying, followed by $m$ integers --- turtles that are lying. Turtles can be printed in any order. If there are different sets of $m$ lying turtles, then print any of them.
3 2 0 0 2 2 2
1 3
5 0 2 0 3 2 1 1 2 4 0
2 1 4
ICPC > Regionals > Northern Eurasia > Northern Eurasia Finals > NEERC 2004 J번