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

#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)
{
    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);
}
uint Now[1000005],Pre[1000005],Nxt[1000005];
bol Onit[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]
        ||Onit[std::min(p[Pre][Now],p[Nxt][Nxt][Now])*n+std::max(p[Pre][Now],p[Nxt][Nxt][Now])])p=p[Nxt];
    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 upd(p[Pre],len-2),upd4(a,b,c,d);
}
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;
        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 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;
                for(uint t=0;t<len;t++)Onit[std::min(Now[t],Now[(t+1)%len])*n+std::max(Now[t],Now[(t+1)%len])]=true;
                upd(0,len);
                for(uint t=0;t<len;t++)Onit[std::min(Now[t],Now[(t+1)%len])*n+std::max(Now[t],Now[(t+1)%len])]=false;
                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;
}

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