liceu

#include <bits/stdc++.h>
using namespace std;
struct liceu
{
    int x1, y1, x2, y2;
}pozscrt[15501];
struct liceu1
{
    int x, y, val;
    bool operator <(const liceu1& other) const
    {
        return val > other.val;
    }
}aux, aux1, aux2;
struct liceu2
{
    int x, y;
}traseumag[160001], traseumagclas[160001], traseuclasa[160001];
priority_queue <liceu1> q;
int n, z, s, t, i, x, y, xm, ym, dismag, d, minpasi, k, dclasa, dmagclasa;
int j, ii, jj, d1;
int a[405][405], scurtaturi[401][401];
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
void lee(int x1, int y1, int x2, int y2)
{
    aux.x = x1;
    aux.y = y1;
    aux.val = 1;
    a[aux.x][aux.y] = 1;
    q.push(aux);
    while(!q.empty())
    {
        aux = q.top();
        q.pop();
        for(k = 0; k < 4; k++)
        {
            aux1.x = aux.x + dx[k];
            aux1.y = aux.y + dy[k];
            if(a[aux1.x][aux1.y] == 0)
            {
                a[aux1.x][aux1.y] = a[aux.x][aux.y] + 1;
                aux1.val = a[aux1.x][aux1.y];
                if(scurtaturi[aux1.x][aux1.y] != 0)
                {
                    aux2.x = pozscrt[scurtaturi[aux1.x][aux1.y]].x1;
                    aux2.y = pozscrt[scurtaturi[aux1.x][aux1.y]].y1;
                    if(a[aux2.x][aux2.y] == 0)
                    {
                        a[aux2.x][aux2.y] = aux2.val = a[aux.x][aux.y] + 2;
                        q.push(aux2);
                    }
                    else q.push(aux1);
                    aux2.x = pozscrt[scurtaturi[aux1.x][aux1.y]].x2;
                    aux2.y = pozscrt[scurtaturi[aux1.x][aux1.y]].y2;
                    if(a[aux2.x][aux2.y] == 0)
                    {
                        a[aux2.x][aux2.y] = aux2.val = a[aux.x][aux.y] + 2;
                        q.push(aux2);
                    }
                    else q.push(aux1);
                }
                else q.push(aux1);
            }
        }
    }
}
int main()
{
    ifstream f("liceu.in");
    ofstream g("liceu.out");
    f >> n >> z >> s >> t;
    for(i = 1; i <= z; i++)
    {
        f >> x >> y;
        a[x][y] = -1;
    }
    for(i = 1; i <= s; i++)
    {
        f >> pozscrt[i].x1 >> pozscrt[i].y1 >> pozscrt[i].x2 >> pozscrt[i].y2;
        scurtaturi[pozscrt[i].x1][pozscrt[i].y1] = scurtaturi[pozscrt[i].x2][pozscrt[i].y2] = i;
    }
    f >> xm >> ym;
    for(i = 0; i <= n + 1; i++)
        a[0][i] = a[n + 1][i] = a[i][0] = a[i][n + 1] = -1;
    lee(1, 1, xm, ym);
    dismag = d = a[xm][ym];
    traseumag[d].x = xm;
    traseumag[d].y = ym;
    x = xm;
    y = ym;
    d--;
    while(d > 0)
    {
        d1 = d;
        for(k = 0; k < 4; k++)
        {
            ii = x + dx[k];
            jj = y + dy[k];
            if(a[ii][jj] == d)
            {
                traseumag[d].x = ii;
                traseumag[d].y = jj;
                x = ii;
                y = jj;
                d--;
                break;
            }
        }
        if(d1 == d)
        {
            if(pozscrt[scurtaturi[x][y]].x1 == x && pozscrt[scurtaturi[x][y]].y1 == y)
            {
                traseumag[d].x = ii = pozscrt[scurtaturi[x][y]].x2;
                traseumag[d].y = jj = pozscrt[scurtaturi[x][y]].y2;
                x = ii;
                y = jj;
                d--;
            }
            else
            {
                traseumag[d].x = ii = pozscrt[scurtaturi[x][y]].x1;
                traseumag[d].y = jj = pozscrt[scurtaturi[x][y]].y1;
                x = ii;
                y = jj;
                d--;
            }
        }
    }
    for(i = 1; i <= n; i++)
        for(j = 1; j <= n; j++)
            if(a[i][j] != -1) a[i][j] = 0;
    lee(xm, ym, n, n);
    dmagclasa = d = a[n][n];
    if(dmagclasa + dismag - 1 > t || dismag == 0)
    {
        for(i = 1; i <= n; i++)
            for(j = 1; j <= n; j++)
                if(a[i][j] != -1) a[i][j] = 0;
        lee(1, 1, n, n);
        dclasa = d = a[n][n];
        traseuclasa[d].x = n;
        traseuclasa[d].y = n;
        x = n;
        y = n;
        d--;
        while(d > 0)
        {
            d1 = d;
            for(k = 0; k < 4; k++)
            {
                ii = x + dx[k];
                jj = y + dy[k];
                if(a[ii][jj] == d)
                {
                    traseuclasa[d].x = ii;
                    traseuclasa[d].y = jj;
                    x = ii;
                    y = jj;
                    d--;
                    break;
                }
            }
            if(d1 == d)
            {
                if(pozscrt[scurtaturi[x][y]].x1 == x && pozscrt[scurtaturi[x][y]].y1 == y)
                {
                    traseuclasa[d].x = ii = pozscrt[scurtaturi[x][y]].x2;
                    traseuclasa[d].y = jj = pozscrt[scurtaturi[x][y]].y2;
                    x = ii;
                    y = jj;
                    d--;
                }
                else
                {
                    traseuclasa[d].x = ii = pozscrt[scurtaturi[x][y]].x1;
                    traseuclasa[d].y = jj = pozscrt[scurtaturi[x][y]].y1;
                    x = ii;
                    y = jj;
                    d--;
                }
            }
        }
        g << dclasa << "\n";
        for(i = 1; i <= dclasa; i++)
            g << traseuclasa[i].x << " " << traseuclasa[i].y << "\n";
    }
    else
    {
        g << dismag + dmagclasa - 1 << "\n";
        for(i = 1; i <= dismag; i++)
            g << traseumag[i].x << " " << traseumag[i].y << "\n";
        dmagclasa = d = a[n][n];
        traseumagclas[d].x = n;
        traseumagclas[d].y = n;
        x = n;
        y = n;
        d--;
        while(d > 0)
        {
            d1 = d;
            for(k = 0; k < 4; k++)
            {
                ii = x + dx[k];
                jj = y + dy[k];
                if(a[ii][jj] == d)
                {
                    traseumagclas[d].x = ii;
                    traseumagclas[d].y = jj;
                    x = ii;
                    y = jj;
                    d--;
                    break;
                }
            }
            if(d1 == d)
            {
                if(pozscrt[scurtaturi[x][y]].x1 == x && pozscrt[scurtaturi[x][y]].y1 == y)
                {
                    traseumagclas[d].x = ii = pozscrt[scurtaturi[x][y]].x2;
                    traseumagclas[d].y = jj = pozscrt[scurtaturi[x][y]].y2;
                    x = ii;
                    y = jj;
                    d--;
                }
                else
                {
                    traseumagclas[d].x = ii = pozscrt[scurtaturi[x][y]].x1;
                    traseumagclas[d].y = jj = pozscrt[scurtaturi[x][y]].y1;
                    x = ii;
                    y = jj;
                    d--;
                }
            }
        }
        for(i = 2; i <= dmagclasa; i++)
            g << traseumagclas[i].x << " " << traseumagclas[i].y << "\n";
    }
    return 0;
}