Background

Special for beginners, ^_^

Description

J老师写了n封信并放入n个信封装好，准备寄出。结果小W一时好厅，将这n封信都拿出了信封。 幸好小W还记得第i封信肯定不是装在信封j中。请帮助J老师尽可能多地将信正确地装回信封。

Format

Input

第一行是一个整数n（n≤100）。信和信封依次编号为1，2，…，n。 接下来的各行中每行有2个数i和j，表示第i封信肯定不是装在第j个信封中。文件最后一行是2个0，表示结束。

Output

输出的各行中每行有2个数i和j，用一个空格分开，表示第i封信肯定是装在第j个信封中。 请按信的编号i从小到大顺序输出。若不能确定正确装入信封的任何信件，则输出“none”。

Samples

3
1 2
1 3
2 1
0 0    

1 1

Limitation

1s, 1024KiB for each test case.