27633번 - Concealed Domino 스페셜 저지다국어

There are N dominoes. Each domino is an ordered-pair of two eyes (a_i, b_i) where 1 ≤ a_i, b_i ≤ M. That means a domino (p, q) differs from a domino (q, p) if p ≠ q.

Due to some unknown reasons, each domino is either partially or fully concealed. Specifically, at least an eye is concealed from each domino.

Your task in this problem is to figure out the concealed eyes such that no two dominoes are the same. If it is possible, then you need to output one set of unconcealed dominoes that corresponds to the given input.

For example, let there be N = 3 dominoes with the maximum value of an eye be M = 2 and the dominoes be {(?, ?),(1, ?),(?, 2)}. There are 6 correct answers for this case.

• {(1, 1),(1, 2),(2, 2)}
• {(1, 2),(1, 1),(2, 2)}
• {(2, 1),(1, 1),(1, 2)}
• {(2, 1),(1, 1),(2, 2)}
• {(2, 1),(1, 2),(2, 2)}
• {(2, 2),(1, 1),(1, 2)}

Note that answers such as {(1, 1),(1, 1),(1, 2)} is not correct as the first and second dominoes are the same. Answer such as {(1, 1),(2, 2),(1, 2)} is also not correct as the second domino (2, 2) does not correspond to the input (1, ?).

Input begins with a line containing two integers N M (1 ≤ N ≤ min(100 000, M²); 1 ≤ M ≤ 100, 000) representing the number of dominoes and the maximum value on each eye. The next N lines each contains two integers a_i b_i (a_i, b_i ∈ {−1, 1, 2, . . . , M}; a_i = −1 or b_i = −1) representing the ordered-pair of eyes of the i^th domino. If a_i or b_i equals to −1, then it means the respective value is unknown.

If all concealed eyes can be determined such that no two dominoes are the same, then output starts with “YES” (without quotes) in a line. The next N lines each contains two integers pi qi representing the ordered-pair of eyes of the i^th domino. The order of dominoes in the output should be the same as the input. If there is more than one correct answer, you may output any one of them.

If the concealed eyes cannot be determined, then output “NO” (without quotes) in a line.