Number Friends
Output: Standard Output (stdout)
Memory limit: 256 megabytes
Time limit: 2.0 seconds
The natural numbers are making friends! Each number is allowed to befriend another number which is a multiple of itself and does not yet have friends.
Numbers love a good order, so they take turns in a predetermined sequence. When it is a number's turn, it will always befriend the smallest number that it is allowed to.
Here's an example of such a sequence:
1 3 1
Firstly, number 1 would befriend the smallest multiple of itself, which is 2. Secondly, the number 3 would befriend the smallest multiple of itself, which is 6. The number 1 is in the sequence for the second time, but cannot befriend 2 or 3 as they already have friends, so befriends 4 instead.
You are given a list of N friendships between pairs of numbers and want to reverse engineer the order in which the friendships were made. Where there are multiple possibilities, the lexicographically smallest sequence should be given  see the explanation of the sample for an example.
Input
The first line will contain a single integer N, with 1 \leq N \leq 100000.
N lines will follow, each containing two integers a, b, indicating that there is a friendship between numbers a and b, with a<b and 1 \leq a \leq 10^9. For C++ users note that b may not fit in a 32 bit integer.
Output
Print the lexicographically smallest sequence of numbers that generate the friendships in the input. It is guaranteed that at least one such sequence exists.
Subtasks
 Subtask 1 (15%): N \leq 3
 Subtask 2 (15%): N \leq 4
 Subtask 3 (30%): N \leq 1000
 Subtask 4 (40%): No constraints.
Explanation
There are two sequences that generate the friendships seen in the sample input, 1,3,1 and 3,1,1. The lexicographically smaller of the two is 1,3,1, so that is the output.

Sample Input 1
3 1 4 1 2 3 6
Sample Output 1
1 3 1