/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
下の階から順に 1, 2, \ldots, 2N の番号がついた 2N 階から成る建物があります。
この建物のエレベーターが 1 度だけ 1 階から 2N 階まで動きました。
この途中で、 N 人が乗り降りしました。人 i (1 \leq i \leq N) は、それぞれエレベーターに A_i 階で乗り、B_i 階で降りました。ただし、1 \leq A_i < B_i \leq 2N であり、それぞれの階で乗り降りした人はただ 1 人です。
また、この N 人は気難しいため、以下の条件が満たされていました。
- 人 i (1 \leq i \leq N) がエレベーターに乗っているとき、他の人が乗り降りした回数を C_i (= B_i - A_i - 1) で表すと、次の条件が成り立つ
- 人 i と人 j が同時にエレベーターに乗っていた瞬間が存在するならば、C_i = C_j である
A, B は記録されていましたが、残念なことに、記録の一部が消えてしまいました。A_i, B_i が消えている場合は -1 として与えられます。
また、残っている記録も誤っている可能性があります。
残っている記録に矛盾しないような A, B の組み合わせが存在するかどうか判定してください。
制約
- 1 \leq N \leq 100
- A_i = -1 または 1 \leq A_i \leq 2N
- B_i = -1 または 1 \leq B_i \leq 2N
- 入力は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
N A_1 B_1 A_2 B_2 : A_N B_N
出力
残っている記録に矛盾しないような A, B の組み合わせが存在する場合は Yes を、しない場合は No を出力せよ。
入力例 1
3 1 -1 -1 4 -1 6
出力例 1
Yes
例えば、B_1 = 3, A_2 = 2, A_3 = 5 であった場合、全ての条件を満たします。
この場合、人 1, 2 が同時にエレベーターに乗っている瞬間がありますが、C_1 = C_2 = 1 であるので問題ありません。
入力例 2
2 1 4 2 3
出力例 2
No
人 1, 2 が同時にエレベーターに乗っている瞬間がありますが、C_1 = 2, C_2 = 0 なのでいずれかの情報が誤っています。
入力例 3
2 4 1 2 4
出力例 3
No
記録は全て残っているように見えますが、明らかに誤っています。
Score : 600 points
Problem Statement
There is a building with 2N floors, numbered 1, 2, \ldots, 2N from bottom to top.
The elevator in this building moved from Floor 1 to Floor 2N just once.
On the way, N persons got on and off the elevator. Each person i (1 \leq i \leq N) got on at Floor A_i and off at Floor B_i. Here, 1 \leq A_i < B_i \leq 2N, and just one person got on or off at each floor.
Additionally, because of their difficult personalities, the following condition was satisfied:
- Let C_i (= B_i - A_i - 1) be the number of times, while Person i were on the elevator, other persons got on or off. Then, the following holds:
- If there was a moment when both Person i and Person j were on the elevator, C_i = C_j.
We recorded the sequences A and B, but unfortunately, we have lost some of the records. If the record of A_i or B_i is lost, it will be given to you as -1.
Additionally, the remaining records may be incorrect.
Determine whether there is a pair of A and B that is consistent with the remaining records.
Constraints
- 1 \leq N \leq 100
- A_i = -1 or 1 \leq A_i \leq 2N.
- B_i = -1 or 1 \leq B_i \leq 2N.
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N A_1 B_1 A_2 B_2 : A_N B_N
Output
If there is a pair of A and B that is consistent with the remaining records, print Yes; otherwise, print No.
Sample Input 1
3 1 -1 -1 4 -1 6
Sample Output 1
Yes
For example, if B_1 = 3, A_2 = 2, and A_3 = 5, all the requirements are met.
In this case, there is a moment when both Person 1 and Person 2 were on the elevator, which is fine since C_1 = C_2 = 1.
Sample Input 2
2 1 4 2 3
Sample Output 2
No
There is a moment when both Person 1 and Person 2 were on the elevator. Since C_1 = 2, C_2 = 0, some of the information is incorrect.
Sample Input 3
2 4 1 2 4
Sample Output 3
No
The records are seemingly intact but clearly are incorrect.