// 那就是希望。
// 即便需要取模，也是光明。

#include <algorithm>
#include <random>
#include <stdio.h>
#include <vector>
typedef long long llt;
typedef unsigned uint;typedef unsigned long long ullt;
typedef bool bol;typedef char chr;typedef void voi;
typedef double dbl;
template<typename T>bol _max(T&a,T b){return(a<b)?a=b,true:false;}
template<typename T>bol _min(T&a,T b){return(b<a)?a=b,true:false;}
template<typename T>T lowbit(T n){return n&-n;}
template<typename T>T gcd(T a,T b){return b?gcd(b,a%b):a;}
template<typename T>T lcm(T a,T b){return(a!=0||b!=0)?a/gcd(a,b)*b:(T)0;}
template<typename T>T exgcd(T a,T b,T&x,T&y){if(b!=0){T ans=exgcd(b,a%b,y,x);y-=a/b*x;return ans;}else return y=0,x=1,a;}
template<typename T>T power(T base,T index,T mod)
{
    T ans=1%mod;
    while(index)
    {
        if(index&1)ans=ans*base%mod;
        base=base*base%mod,index>>=1;
    }
    return ans;
}
// Heaven and Earth... My guiding star...
// Akira Complex R.I.P.
bol B[1005][1005],B2[1005][1005],G[1000005];
uint E[2][1000005],Tp[1000005],Ops[4][1000005],n,m,tp;
voi doit(uint a,uint b,uint c,uint d)
{
    // printf("%u %u %u %u\n",a+1,b+1,c+1,d+1);
    if(a==b||b==c||c==d||d==a||a==c||b==d)puts("qvq"),exit(233);
    if(B[a][c]||B[b][d]||!B[a][b]||!B[c][d])puts("qwq"),exit(233);
    // for(uint i=0;i<n;i++,putchar('\n'))
    //     for(uint j=0;j<n;j++)putchar("01"[B[i][j]]);
    Ops[0][tp]=a,Ops[1][tp]=b,Ops[2][tp]=c,Ops[3][tp]=d,tp++;
    B[a][c]=B[c][a]=B[b][d]=B[d][b]=true,B[a][b]=B[b][a]=B[c][d]=B[d][c]=false;
}
voi upd4(uint a,uint b,uint c,uint d)
{
    // for(auto p:{a,b,c,d})
    // {
    //     for(auto q:{a,b,c,d})putchar("01"[B[p][q]]);
    //     puts("");
    // }
    if(B[a][b]!=B[c][d]||B[a][d]!=B[b][c]||B[a][b]==B[a][d])return;
    if(B[a][b])doit(a,b,d,c);else doit(b,c,a,d);
    // for(auto p:{a,b,c,d})
    // {
    //     for(auto q:{a,b,c,d})putchar("01"[B[p][q]]);
    //     puts("");
    // }
}
uint Now[1000005],Pre[1000005],Nxt[1000005];
voi upd(uint p,uint len)
{
    if(len<4)exit(233);
    if(len==4){upd4(p[Now],p[Nxt][Now],p[Nxt][Nxt][Now],p[Pre][Now]);return;}
    // p=p[Nxt];
    while(p[Now]==p[Nxt][Now]||p[Now]==p[Nxt][Nxt][Now]||p[Now]==p[Pre][Now]
        ||p[Nxt][Now]==p[Nxt][Nxt][Now]||p[Nxt][Now]==p[Pre][Now]||p[Nxt][Nxt][Now]==p[Pre][Now])p=p[Nxt];
    // std::vector<uint>V;
    // for(uint t=p;;t=Nxt[t]){V.push_back(B[Now[Nxt[t]]][Now[t]]);if(Nxt[t]==p)break;}
    uint a=p[Now],b=p[Nxt][Now],c=p[Nxt][Nxt][Now],d=p[Pre][Now];p[Pre][Nxt]=p[Nxt][Nxt],p[Nxt][Nxt][Pre]=p[Pre];
    if(B[a][b]==B[c][d])upd4(a,b,c,d),upd(p[Pre],len-2);
    else
    {
        // for(uint t=p[Pre];;t=Nxt[t])
        // {
        //     if((Now[t]==a&&Now[Nxt[t]]==b)||(Now[t]==b&&Now[Nxt[t]]==a))puts("qrq"),exit(0);
        //     if(Nxt[t]==p[Pre])break;
        // }
        // uint x=B[a][b],y=B[c][d];
        upd(p[Pre],len-2);
        // printf("%u %u %u %u\n",x,y,(uint)B[a][b],(uint)B[c][d]);
        // if(B[a][b]!=B[c][d])puts("qwqwq");
        upd4(a,b,c,d);
    }
    // p[Pre][Nxt]=p,p[Nxt][Nxt][Pre]=p[Nxt];
    // for(auto s:V)putchar("01"[s]);
    // puts("");
    // for(uint t=p;;t=Nxt[t]){putchar("01"[B[Now[Nxt[t]]][Now[t]]]);if(Nxt[t]==p)break;}
    // puts("");
}
int main()
{
#ifdef MYEE
    freopen("QAQ.in","r",stdin);
    freopen("QAQ.out","w",stdout);
#else
#endif
    std::mt19937 rng(114514);
    scanf("%u%u",&n,&m);
    for(uint i=0,u,v;i<m;i++)scanf("%u%u",&u,&v),u--,v--,B[u][v]=B[v][u]=true;
    for(uint i=0,u,v;i<m;i++)scanf("%u%u",&u,&v),u--,v--,B2[u][v]=B2[v][u]=true;
    while(true)
    {
        bol f=true;
        for(uint e=0;e<n*n;e++)Tp[e]=0;
        for(uint i=0;i<n;i++)
        {
            std::vector<uint>X,Y;
            for(uint j=0;j<n;j++)if(B[i][j]!=B2[i][j])(B[i][j]?X:Y).push_back(j);
            if(X.size()!=Y.size())return puts("-1"),0;
            for(uint j=0,a,b;j<X.size();j++)
                a=std::min(i,X[j])*n+std::max(i,X[j]),
                b=std::min(i,Y[j])*n+std::max(i,Y[j]),
                E[Tp[a]++][a]=b,E[Tp[b]++][b]=a,f=false;
        }
        if(f)break;
        // for(uint i=0;i<n*n;i++)if(Tp[i]&&(B[i/n][i%n]==B[E[0][i]/n][E[0][i]%n]||B[i/n][i%n]==B[E[1][i]/n][E[1][i]%n]))
        //     exit(233);
        static uint R[2005];for(uint j=0;j<n*2;j++)R[j]=-1;
        for(uint e=0;e<n*n;e++)if(Tp[e]&&!G[e])
        {
            std::vector<uint>Q{e},T;
            do G[Q.back()]=true,Q.push_back(E[Q.size()==1||Q[Q.size()-2]==E[0][Q.back()]][Q.back()]);while(Q.back()!=e);
            for(uint i=0;i+1<Q.size();i++)Q[i]=Q[i]/n==Q[i+1]/n||Q[i]/n==Q[i+1]%n?Q[i]/n:Q[i]%n;
            Q.pop_back();
            if(rng()&1)std::reverse(Q.begin(),Q.end());
            Q.push_back(Q[0]);
            // for(auto s:Q)printf("%u ",s+1);
            // puts("");
            // printf("%u\n",(uint)Q.size());
            for(auto q:Q)if(~R[q<<1|(T.size()&1)])
            {
                uint f=R[q<<1|(T.size()&1)];
                uint len=T.size()-f;
                for(uint t=0;t<len;t++)Now[t]=T[t+f],Pre[t]=t?t-1:len-1,Nxt[t]=t==len-1?0:t+1;
                upd(0,len);
                for(uint t=f+1;t<T.size();t++)R[T[t]<<1|(t&1)]=-1;
                T.resize(f+1);
            }
            else R[q<<1|(T.size()&1)]=T.size(),T.push_back(q);
            R[T[0]<<1]=-1;
        }
    }
    for(uint i=0;i<n;i++)for(uint j=0;j<n;j++)
        if(B[i][j]!=B2[i][j])exit(233);
    printf("%u\n",tp);
    for(uint i=0;i<tp;i++)
        printf("%u %u %u %u\n",Ops[0][i]+1,Ops[1][i]+1,Ops[2][i]+1,Ops[3][i]+1);
    // for(uint i=0;i<n;i++,putchar('\n'))
    //     for(uint j=0;j<n;j++)putchar("01"[B[i][j]]);
    // for(uint i=0;i<n;i++,putchar('\n'))
    //     for(uint j=0;j<n;j++)putchar("01"[B2[i][j]]);
    return 0;
}

// 那就是希望。
// 即便需要取模，也是光明。