matita.cpp

#include <stdio.h>
#include <algorithm>
#include <vector>

int main()
{
  FILE *in=fopen("input.txt","r"),*out=fopen("output.txt","w");
  int N,M,start,end;
  fscanf(in,"%d %d %d %d",&N,&M,&start,&end);
  start--;
  end--;
  std::vector< std::vector<int> >arch(N);
  std::vector<int>path;
  path.reserve(M+1);
 for(int x=0;x<M;x++)
  {
    int a,b;
    fscanf(in,"%d %d",&a,&b);
    a--;
    b--;
    arch[a].push_back(b);
    arch[b].push_back(a);
  }
  int resarch=M,act=start;
  auto ins=path.begin();
  ins=path.insert(ins,act)+1;
  while(resarch)
  {
    while(arch[act].size()>0)
    {
      //printf("%d\n",act);
      int next=arch[act].back();
      arch[act].pop_back();
      arch[next].erase(std::find(arch[next].begin(),arch[next].end(),act));
      resarch--;
      act=next;
      ins=path.insert(ins,act)+1;
    }
    if(resarch)
    {
      act=-1;
      auto x=path.begin();
      for(;x<path.end();x++)if(arch[*x].size()){act=*x;break;}
      ins=x+1;
    }
  }
  for(auto x=path.begin();x<path.end()-1;)
  {
    fprintf(out,"%d ",*x+1);
    x++;
    fprintf(out,"%d\n",*x+1);
  }
}