#include <fstream>
#include <vector>

using namespace std;

const int NMAX = 40000;
const int K = 200;

int vecin[1 + NMAX][2];
int vecinK[1 + NMAX][2];

inline int dirLibera(int nod)
{
  if (vecin[nod][0] == 0)
    return 0;
  if (vecin[nod][1] == 0)
    return 1;
  return -1;
}

inline int next(int &nod, int &ant)
{
  if (vecin[nod][0] == ant)
  {
    ant = nod;
    nod = vecin[nod][1];
    return 1;
  }
  else
  {
    ant = nod;
    nod = vecin[nod][0];
    return 0;
  }
}

inline int nextK(int &nod, int &ant)
{
  if (vecinK[nod][0] == ant)
  {
    ant = nod;
    nod = vecinK[nod][1];
    return 1;
  }
  else
  {
    ant = nod;
    nod = vecinK[nod][0];
    return 0;
  }
}

inline int dist(int nod, int dir, int d)
{
  int ant = nod;

  nod = vecinK[nod][dir];
  while (d >= K)
    dir = nextK(nod, ant), d -= K;

  nod = vecin[ant][dir];
  while (d > 0)
    next(nod, ant), d -= 1;

  return ant;
}

inline int capat(int nod, int dir)
{
  int ant = nod;

  nod = vecinK[nod][dir];
  while (nod != 0)
    dir = nextK(nod, ant);

  nod = vecin[ant][dir];
  while (nod != 0)
    next(nod, ant);

  return ant;
}

bool cautaLant(int a, int b, int dirA, int &stAnt, int &st, int &drAnt, int &dr)
{
  if (vecinK[a][1 - dirA] != 0)
  {
    stAnt = vecinK[a][1 - dirA];
    if (vecinK[stAnt][0] == a)
      st = vecin[stAnt][0];
    else
      st = vecin[stAnt][1];
    drAnt = a;
    dr = b;

    return true;
  }
  else
  {
    int lungime = 0;
    stAnt = b;
    st = a;
    while (st != 0)
    {
      lungime++;
      next(st, stAnt);
    }
    swap(st, stAnt);

    drAnt = a;
    dr = b;
    while (dr != 0 && lungime < K)
    {
      lungime++;
      next(dr, drAnt);
    }

    return lungime == K;
  }
}

bool adaugaMuchie(int a, int b)
{
  int dirA = dirLibera(a);
  int dirB = dirLibera(b);

  if (dirA == -1 || dirB == -1) return false;
  if (capat(a, 1 - dirA) == b) return false;

  vecin[a][dirA] = b;
  vecin[b][dirB] = a;

  int st = -1;
  int dr = -1;
  int stAnt = -1;
  int drAnt = -1;

  if (cautaLant(a, b, dirA, stAnt, st, drAnt, dr))
  {
    while (st != b && dr != 0)
    {
      dirA = (vecin[st][0] == stAnt ? 1 : 0);
      dirB = (vecin[dr][0] == drAnt ? 0 : 1);
      vecinK[st][dirA] = dr;
      vecinK[dr][dirB] = st;

      next(st, stAnt);
      next(dr, drAnt);
    }
  }

  return true;
}

bool stergeMuchie(int a, int b)
{
  if (vecin[a][0] != b && vecin[a][1] != b) return false;

  int dirA = (vecin[a][0] == b ? 0 : 1);
  int dirB;

  int st = -1;
  int dr = -1;
  int stAnt = -1;
  int drAnt = -1;

  if (cautaLant(a, b, dirA, stAnt, st, drAnt, dr))
  {
    while (st != b && dr != 0)
    {
      dirA = (vecin[st][0] == stAnt ? 1 : 0);
      dirB = (vecin[dr][0] == drAnt ? 0 : 1);
      vecinK[st][dirA] = 0;
      vecinK[dr][dirB] = 0;

      next(st, stAnt);
      next(dr, drAnt);
    }
  }

  if (vecin[a][0] == b)
    vecin[a][0] = 0;
  else
    vecin[a][1] = 0;

  if (vecin[b][0] == a)
    vecin[b][0] = 0;
  else
    vecin[b][1] = 0;

  return true;
}

pair<int, int> gasesteDist(int nod, int d)
{
  int st = dist(nod, 0, d);
  int dr = dist(nod, 1, d);

  if (st == dr)
    dr = 0;
  if (st > dr)
    swap(st, dr);

  return make_pair(st, dr);
}

pair<int, int> gasesteCapete(int nod)
{
  int st = capat(nod, 0);
  int dr = capat(nod, 1);

  if (st == dr)
    dr = 0;
  if (st > dr)
    swap(st, dr);

  return make_pair(st, dr);
}

int main()
{
  ifstream in("drumuri4.in");
  ofstream out("drumuri4.out");

  int n, m;
  in >> n >> m;

  for (int i = 1; i <= m; i++)
  {
    int tip;
    in >> tip;

    if (tip == 1)
    {
      int a, b;
      in >> a >> b;

      out << (int)adaugaMuchie(a, b) << '\n';
    }
    else if (tip == 2)
    {
      int a, b;
      in >> a >> b;

      out << (int)stergeMuchie(a, b) << '\n';
    }
    else if (tip == 3)
    {
      int a, d;
      in >> a >> d;

      pair<int, int> sol = gasesteDist(a, d);

      int count = (int)(sol.first != 0) + (int)(sol.second != 0);

      out << count << ' ';
      if (sol.first != 0)
        out << sol.first << ' ';
      if (sol.second != 0)
        out << sol.second << ' ';
      out << '\n';
    }
    else
    {
      int a;
      in >> a;

      pair<int, int> sol = gasesteCapete(a);

      int count = (int)(sol.first != 0) + (int)(sol.second != 0);

      out << count << ' ';
      if (sol.first != 0)
        out << sol.first << ' ';
      if (sol.second != 0)
        out << sol.second << ' ';
      out << '\n';
    }
  }

  return 0;
}