open(IN, "< $ARGV[0]") or die $!;

my $TIMES = $ARGV[1];

my %inter;
my @pairs;
my $n = 0;
while(<IN>)
{
    if(/(\d+)\t(\d+)/)
    {
        my ($node1, $node2) = ($1, $2);
        $inter{$node1}{$node2} = 1;
        $inter{$node2}{$node1} = 1;
        $pairs[$n][1] = $node1;
        $pairs[$n][2] = $node2;
        $n++;
    }
}

my $tmp;
my $randpair1;
my $randpair2;
my $time = 0;
while($time < $TIMES)
{
    # randomly pick a pair of nodes
    # 11 <-> 12, 21 <-> 22
    $randpair1 = int(rand($n));
    $randpair2 = int(rand($n)); 

    
  if(  ($pairs[$randpair1][1] != $pairs[$randpair2][1]) 
    && ($pairs[$randpair1][1] != $pairs[$randpair2][2])
    && ($pairs[$randpair1][2] != $pairs[$randpair2][1])
    && ($pairs[$randpair1][2] != $pairs[$randpair2][2])
    )
  {
    # test if rewiring will be succeed
    if(  ($inter{$pairs[$randpair1][1]}{$pairs[$randpair2][1]} != 1) 
      && ($inter{$pairs[$randpair1][2]}{$pairs[$randpair2][2]} != 1)
      )
    {
        # rewire 11 <-> 21 && 12 <-> 22
        $inter{$pairs[$randpair1][1]}{$pairs[$randpair1][2]} = 0;
        $inter{$pairs[$randpair1][2]}{$pairs[$randpair1][1]} = 0;
        $inter{$pairs[$randpair2][1]}{$pairs[$randpair2][2]} = 0;
        $inter{$pairs[$randpair2][2]}{$pairs[$randpair2][1]} = 0;

        $inter{$pairs[$randpair1][1]}{$pairs[$randpair2][1]} = 1;
        $inter{$pairs[$randpair2][1]}{$pairs[$randpair1][1]} = 1;
        $inter{$pairs[$randpair1][2]}{$pairs[$randpair2][2]} = 1;
        $inter{$pairs[$randpair2][2]}{$pairs[$randpair1][2]} = 1;

        # update @pairs
        $tmp = $pairs[$randpair1][2];
        $pairs[$randpair1][2] = $pairs[$randpair2][1];
        $pairs[$randpair2][1] = $tmp;
        
        $time++;
    }
    elsif(  ($inter{$pairs[$randpair1][1]}{$pairs[$randpair2][2]} != 1) 
         && ($inter{$pairs[$randpair2][1]}{$pairs[$randpair1][2]} != 1)
         )
    {
        # rewire 11 <-> 22 && 21 <-> 12
        $inter{$pairs[$randpair1][1]}{$pairs[$randpair1][2]} = 0;
        $inter{$pairs[$randpair1][2]}{$pairs[$randpair1][1]} = 0;
        $inter{$pairs[$randpair2][1]}{$pairs[$randpair2][2]} = 0;
        $inter{$pairs[$randpair2][2]}{$pairs[$randpair2][1]} = 0;

        $inter{$pairs[$randpair1][1]}{$pairs[$randpair2][2]} = 1;
        $inter{$pairs[$randpair2][2]}{$pairs[$randpair1][1]} = 1;
        $inter{$pairs[$randpair1][2]}{$pairs[$randpair2][1]} = 1;
        $inter{$pairs[$randpair2][1]}{$pairs[$randpair1][2]} = 1;

        # update @pairs
        $tmp = $pairs[$randpair1][2];
        $pairs[$randpair1][2] = $pairs[$randpair2][2];
        $pairs[$randpair2][2] = $tmp;
    
        $time++;
    } 
  }
}

open(OUT, "> $ARGV[2]") or die $!;
foreach my $p (0 ... ($n - 1))
{
    print(OUT "$pairs[$p][1]\t$pairs[$p][2]\n");
}