Training Site
Sideways banner

Number Friends

Input: Standard Input (stdin)
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 pre-determined 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.


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.


Print the lexicographically smallest sequence of numbers that generate the friendships in the input. It is guaranteed that at least one such sequence exists.


  • Subtask 1 (15%): N \leq 3
  • Subtask 2 (15%): N \leq 4
  • Subtask 3 (30%): N \leq 1000
  • Subtask 4 (40%): No constraints.


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

    1 4
    1 2
    3 6

    Sample Output 1

    1 3 1