# Codeforces847a union ofdoubly linked lists

Posted by yjjr's blog on February 6, 2018

Doublylinked list is one of the fundamental data structures. A doubly linked list isa sequence of elements, each containing information about the previous and thenext elements of the list. In this problem all lists have linear structure.I.e. each element except the first has exactly one previous element, eachelement except the last has exactly one next element. The list is not closed ina cycle.

In thisproblem you are given n memorycells forming one or more doubly linked lists. Each cell contains informationabout element from some list. Memory cells are numbered from 1 to n.

For eachcell i you are given twovalues:

·  li — cell containing previous element for theelement in the cell i;

·  ri — cell containing next element for theelement in the cell i.

If cell i contains informationabout the element which has no previous element thenli = 0.Similarly, if cell i containsinformation about the element which has no next element then ri = 0. Three lists are shown on the picture.

Forexample, for the picture above the values of l and r are thefollowing: l1 = 4,r1 = 7; l2 = 5, r2 = 0; l3 = 0, r3 = 0; l4 = 6, r4 = 1; l5 = 0, r5 = 2; l6 = 0, r6 = 4; l7 = 1, r7 = 0.

Your taskis to unite all given lists in a single list, joining them to each other in anyorder. In particular, if the input data already contains a single list, thenthere is no need to perform any actions. Print the resulting list in the formof values liri.

Any otheraction, other than joining the beginning of one list to the end of another, cannot be performed.

Input

The firstline contains a single integer n (1 ≤ n ≤ 100) — the number ofmemory cells where the doubly linked lists are located.

Each ofthe following n linescontains two integers liri (0 ≤ li, ri ≤ n) — thecells of the previous and the next element of list for cell i. Value li = 0 if element in cell i has no previouselement in its list. Value ri = 0 if elementin cell i has no next elementin its list.

It isguaranteed that the input contains the correct description of a single or moredoubly linked lists. All lists have linear structure: each element of listexcept the first has exactly one previous element; each element of list exceptthe last has exactly one next element. Each memory cell contains informationabout one element from some list, each element of each list written in one of n given cells.

Output

Print n lines, the i-th line must contain two integers li and ri — the cells of theprevious and the next element of list for cell i after all lists from the input are united ina single list. If there are many solutions print any of them.

Example

Input

7
4 7
5 0
0 0
6 1
0 2
0 4
1 0

Output

4 7
5 6
0 5
6 1
3 2
2 4
1 0

Code

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
using namespace std;

int n,l,r,cnt=0;

inline bool checkl(int x,int y)
{
if(l[x]==0)return1;
elseif(l[x]==y)return 0;
returncheckl(l[x],y);
}

inline bool checkr(int x,int y)
{
if(r[x]==0)return1;
elseif(r[x]==y)return 0;
returncheckr(r[x],y);
}

int main()
{
scanf("%d",&n);
rep(i,1,n){scanf("%d%d",&l[i],&r[i]);if(l[i]==0)cnt++;}
rep(i,1,n){
//     cout<<cnt<<endl;
if(l[i]==0&&cnt>1)
rep(j,1,n)if(r[j]==0&&i!=j&&checkr(i,j)){r[j]=i;l[i]=j;cnt--;break;}
if(r[i]==0&&cnt>1)
rep(j,1,n)if(l[j]==0&&i!=j&&checkl(i,j)&&checkr(i,j)){l[j]=i;r[i]=j;cnt--;break;}
}
rep(i,1,n)printf("%d%d\n",l[i],r[i]);
return0;
} 