2679. Windy Office

单点时限: 2.0 sec

内存限制: 256 MB

Senior chief programmer Andy and his team just finished a large software project. They printed the entire source code and left it on the table while they went for a lunch. Unfortunately they left the window in the office open and it was a windy day. When they returned from the lunch they found out that the wind had scattered the papers all over the office. Now they want to arrange them in the original order.

Andy is a man of action. He immediately numbered all the pages he could find. Of course this numbering is not related to the original order of the pages. The source code consists of several procedures, each labeled with a unique number. A procedure starts at some page and can span across several consecutive pages. The first and the last of these pages can contain also other procedures or their parts. The procedure labels are not related to the order of the procedures in the program.

Now the whole team is sitting in the office examining all the papers found and writing pairs of numbers to the large whiteboard. The first number in each pair represents the number of the page (in Andy’s numbering) and the second number represents procedure label. Such a pair means that a part of the given procedure (or the entire procedure) is on the given page. It is very likely that some pairs are missing. In spite of this Andy hopes that this information would help them to recover the original order of the pages.

输入格式

Input consists of multiple blocks. Each block begins with a line containing integer N giving the number of pairs noted on the whiteboard. This line is followed by N pairs of numbers ai, bi, where ai is the number of the page and bi is the label of the procedure. You may assume that both numbers of pages and labels of procedures are positive integers smaller than 1 000 000 000. There is a blank line after each block.

输出格式

For each block of the input give one possible ordering of the pages found. The output is a permutation of all page numbers mentioned at least once in the input. If there is no such ordering (due to the errors on the whiteboard made by the poor tired programmers) write only the word NO.

Note: Some mailer programs do not send files with lines longer than 70 characters correctly. You are allowed and encouraged to split long lines into several lines on any whitespace.

样例

Input
8
20 50
30 40
10 20
10 40
20 30
10 10
40 30
10 30
6
11 1
11 2
21 2
21 3
31 3
31 1
6
1 1
2 2
3 3
4 1
4 2
4 3
2
1 1
2 2
Output
20 40 10 30
NO
NO
2 1

0 人解决,2 人已尝试。

0 份提交通过,共有 13 份提交。

9.9 EMB 奖励。

创建: 10 年,5 月前.

修改: 2 年,6 月前.

最后提交: 4 年,4 月前.

来源: IPSC 2000

题目标签