#include <bits/stdc++.h>
using namespace std;
#define PB push_back
#define ZERO (1e-10)
#define INF int(1e9+1)
#define CL(A,I) (memset(A,I,sizeof(A)))
#define DEB printf("DEB!\n");
#define D(X) cout<<"  "<<#X": "<<X<<endl;
#define EQ(A,B) (A+ZERO>B&&A-ZERO<B)
typedef long long ll;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef vector<ii> vii;
#define IN(n) int n;scanf("%d",&n);
#define FOR(i, m, n) for (int i(m); i < n; i++)
#define F(n) FOR(i,0,n)
#define FF(n) FOR(j,0,n)
#define FT(m, n) FOR(k, m, n)
#define aa first
#define bb second
void ga(int N,int *A){F(N)scanf("%d",A+i);}
#define MX (1<<18)
#define LG (21)
#define VL (B[i]>>(s*8)&255)
struct DC{
    map<ii,int> E;
    bitset<MX> Z[LG],f[LG];
    int I,A[MX],B[MX],X[MX],T[MX],L[LG],U[LG][MX*2];
    int p[LG][MX*2],w[LG][MX],g[LG][MX*2],t[LG][MX*2],O[LG];
    void CLR(){CL(*w,-1),I=0,E.clear(),CL(O,0),Z[0].reset(),f[0].reset();}
    void ADD(int a,int b){A[I]=a,B[I]=b,T[I]=INF,E[minmax(a,b)]=I,X[I++]=1;}
    void DEL(int a,int b){A[I]=a,B[I]=b,T[E[minmax(a,b)]]=I,X[I++]=-1;}
    void QY(int a,int b){A[I]=a,B[I]=b,X[I++]=0;}
    void GO(vi&o){*L=0;F(MX)U[0][L[0]++]=i;rec(0,I-1,1,o);}
    void ADD(int d,int a,int b,int T){p[d][O[d]]=w[d][a],g[d][O[d]]=b,t[d][O[d]]=T,w[d][a]=O[d]++;}
    void cl(int d){if(d)F(L[d-1])Z[d][U[d-1][i]]=f[d][U[d-1][i]]=0;}
    void cs(int*A,int N,int s){
        static int B[MX*2];
        static int C[256];
        CL(C,0),--*C,memcpy(B,A,N*sizeof(int));
        F(N)++C[VL];
        FT(1,256)C[k]+=C[k-1];
        for(int i=N-1;~i;--i)A[C[VL]--]=B[i];
    }
   void rs(int*A,int N){
        if(N<80)return sort(A,A+N);
        F(3)cs(A,N,i);
    }
    void dfs(int u,int D,int I,int d){
        if(f[d][u]||u==D)return;
        f[d][u]=1;
        if(Z[d][u])ADD(d,u,D,INF),ADD(d,D,u,INF),f[d][u]=0;
        else for(int j=w[d-1][u];~j;j=p[d-1][j])if(t[d-1][j]>=I)dfs(g[d-1][j],D,I,d);
    }
    void rec(int b,int e,int d,vi&o){
        O[d]=L[d]=0;
        int S=0,M=(b+e+1)/2;
        FT(b,e+1)S+=!X[k],U[d][L[d]++]=A[k],U[d][L[d]++]=B[k];
        if(!S)return;
        rs(U[d],L[d]),L[d]=unique(U[d],U[d]+L[d])-U[d];
        F(L[d])w[d][U[d][i]]=-1,Z[d][U[d][i]]=1;
        F(L[d])for(int j=w[d-1][U[d][i]];~j;j=p[d-1][j])if(t[d-1][j]>=b){
            if(Z[d][g[d-1][j]])ADD(d,U[d][i],g[d-1][j],t[d-1][j]);
            else dfs(g[d-1][j],U[d][i],b,d);
        }
        if(b==e)return o.PB(!!~w[d][A[b]]),cl(d);
        rec(b,M-1,d+1,o);
        FT(b,M)if(X[k]>0)ADD(d,A[k],B[k],T[k]),ADD(d,B[k],A[k],T[k]);
        rec(M,e,d+1,o),cl(d);
    }
}T;
int N,Q,A[MX],X[MX],Y[MX],V[MX],O[MX];
set<ii> F;
vi o;
int main(void){
    scanf("%d%d",&N,&Q),CL(O,-1);
    F(Q){
        scanf("%d%d%d",A+i,X+i,Y+i);
        if(!A[i])scanf("%d",V+i);
    }
    FF(10){
        T.CLR(),F.clear();
        F(Q)if(!A[i]){
                if(V[i]<=j)T.ADD(X[i],Y[i]),F.insert(minmax(X[i],Y[i]));
            }else if(A[i]^1)T.QY(X[i],Y[i]);
            else if(F.count(minmax(X[i],Y[i])))T.DEL(X[i],Y[i]),F.erase(minmax(X[i],Y[i]));
        o.clear(),T.GO(o);
        F((int)o.size())if(!~O[i]&&o[i])O[i]=j;
    }
    F((int)o.size())printf("%d\n",O[i]);
    return 0;
}