class point{
    int x;
    int y;
    point pi;
    double key;
     int num;
     int arraypos;
    point(int x,int y,point pi,double key,int nu,int apos){
       this.num=nu;
        this.x=x;
        this.y=y;
        this.pi=pi;
        this.key=key;
        this.arraypos=apos;
    }
    void set(int x,int y,point pi,double key,int nu,int apos){
       this.num=nu;
        this.x=x;
        this.y=y;
        this.pi=pi;
        this.key=key;
        this.arraypos=apos;
    }
}
public class Main {

    Main p;
     int heapsize=0,findcount=0;


    /**
     * @param args the command line arguments
     */
     double calweight(point u,point v){
         int x1=u.x;
         int y1=u.y;
         int x2=v.x;
         int y2=v.y;

         int dif1=0,dif2=0;
     if(x1>x2)
                dif1=x1-x2;
                else
                 dif1=x2-x1;
                if(y1>y2)
                dif2=y1-y2;
                else
                 dif2=y2-y1;


               return java.lang.Math.sqrt(dif1^2+dif2^2);

           }
     int contains(point[] q,point v){
         for(int i=1;i<=heapsize;i++){
             if(q[i]==v)
                 return 1;
                 }
         return 0;
    }

    public static void main(String[] args) {
        Main f=new Main();
        Map<Integer,ArrayList<point>> edges=new HashMap<Integer,ArrayList<point>>();

         int x1,x2,y1,y2,dif1,dif2;

         int n=10,m=20,k=80;
         point[] Q=new point[n+1];
         Random rand1=new  Random();
         Random rand2=new  Random();

        for(int i=1;i<=n;i++)
        {

            x1=rand1.nextInt(k+1);
            y1=rand2.nextInt(k+1);
           Q[i]=new point(x1,y1,null,9999,i,i);

        }
         rand1=new  Random();
         rand2=new  Random();
         for(int j=1;j<=m;j++){
             int p1=0,p2=0;
             while(p1==0 || p2==0){
             p1=rand1.nextInt(n+1);
             p2=rand1.nextInt(n+1);
             }
             if(edges.containsKey(p1)){
                 ArrayList x=edges.get(p1);
                 x.add(Q[p2]);
             }
 else{
                 ArrayList<point> y=new ArrayList<point>();
                 y.add(Q[p2]);
                 edges.put(p1,y);
 }
         }

         f.heapsize=Q.length-1;
         while(f.heapsize>0){
             point u=f.extractmin(Q);
             if(u.pi!=null)
                 System.out.println(u.num+" "+u.pi.num);
             else
               System.out.println(u.num);
             if(edges.containsKey(u.num)){

                 for(point v:edges.get(u.num)){

                     if(f.calweight(u, v)<v.key){

                     v.pi=u;
                     v.key=f.calweight(u, v);
                     f.decreasekey(Q,v.arraypos);
                     }

                 }


             }

         }

    }
 void decreasekey(point[] a,int i){


        while(i>1 && a[i].key<a[i/2].key){
          point temp=new point(a[i].x,a[i].y,a[i].pi,a[i].key,a[i].num,a[i].arraypos);
          a[i].set(a[i/2].x, a[i/2].y, a[i/2].pi,a[i/2].key,a[i].num,a[i/2].arraypos);
          a[i/2].set(temp.x, temp.y, temp.pi,temp.key,a[i/2].num,a[i].arraypos);
          i=i/2;

        }
    }
 void max_heapify(point[] a,int i){
       int l=2*i;
       int large=i;
       int r=2*i+1;
       if(l<a.length && a[l].key<a[i].key)
           large=l;
       else
           large=i;
        if(r<a.length && a[r].key<a[i].key)
           large=r;
       if(large!=i){
           point temp=new point(a[i].x,a[i].y,a[i].pi,a[i].key,a[i].num,a[i].arraypos);
           a[i].set(a[large].x, a[large].y, a[large].pi,a[large].key,a[i].num,a[large].arraypos);
          a[large].set(temp.x, temp.y, temp.pi,temp.key,a[large].num,a[i].arraypos);

           max_heapify(a, large);
}
}
  point extractmin(point[] a){
       point min=new point(a[1].x,a[1].y,a[1].pi,a[1].key,a[1].num,a[1].arraypos);
       a[1].set(a[heapsize].x, a[heapsize].y,a[heapsize].pi,a[heapsize].key,a[heapsize].num,1);
       heapsize=heapsize-1;
        max_heapify(a,1);
       return min;
   }