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

#include <algorithm>
#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)
{
    // if(a==b||b==c||c==d||d==a||a==c||b==d)puts("qvq"),exit(233);
    // for(uint i=0;i<n;i++,putchar('\n'))
    //     for(uint j=0;j<n;j++)putchar("01"[B[i][j]]);
    // printf("%u %u %u %u\n",a+1,b+1,c+1,d+1);
    Ops[0][tp]=a,Ops[1][tp]=b,Ops[2][tp]=c,Ops[3][tp]=d,tp++;
    // if(B[a][c]||B[b][d]||!B[a][b]||!B[c][d])puts("qwq"),exit(233);
    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])doit(a,b,d,c);else doit(b,c,a,d);}
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;}
    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];
    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[Nxt][Nxt],len-2);
    else
        upd(p[Nxt][Nxt],len-2),upd4(a,b,c,d);
}
int main()
{
#ifdef MYEE
    freopen("QAQ.in","r",stdin);
    freopen("QAQ.out","w",stdout);
#else
#endif
    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;
    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;
    }
    // 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;
        while(!G[Q.back()])
            G[Q.back()]=true,Q.push_back(E[Q.size()==1||Q[Q.size()-2]==E[0][Q.back()]][Q.back()]);
        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.back()=Q[0];
        // for(auto s:Q)printf("%u ",s+1);
        // puts("");
        // printf("%u\n",(uint)Q.size());
        uint len=Q.size()-1;
        for(uint i=0;i<len;i++)
            Now[i]=Q[i],Pre[i]=i?i-1:len-1,Nxt[i]=(i+1)%len;
        dfs(0,len);
    }
    // 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;
}

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

answer.code: In function ‘int main()’:
answer.code:93:9: error: ‘dfs’ was not declared in this scope
   93 |         dfs(0,len);
      |         ^~~
answer.code:64:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   64 |     scanf("%u%u",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~
answer.code:65:35: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   65 |     for(uint i=0,u,v;i<m;i++)scanf("%u%u",&u,&v),u--,v--,B[u][v]=B[v][u]=true;
      |                              ~~~~~^~~~~~~~~~~~~~
answer.code:66:35: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   66 |     for(uint i=0,u,v;i<m;i++)scanf("%u%u",&u,&v),u--,v--,B2[u][v]=B2[v][u]=true;
      |                              ~~~~~^~~~~~~~~~~~~~