#include <vector>
#include <iostream>
#include <map>

using namespace std;

const double eps = 1e-12; // stała przybliżenia zera
double d = 0.85;

double getXY(map<int, map<int, double>> &macierz_sasiedztwa, int x, int y)
{
    if ((macierz_sasiedztwa.find(x) != macierz_sasiedztwa.end())
        && (macierz_sasiedztwa[x].find(y) != macierz_sasiedztwa[x].end()) )
    {
        return macierz_sasiedztwa[x][y];
    }
    else
        return 0;

}

void setXY(map<int, map<int, double>> &macierz_sasiedztwa, int x, int y, double val)
{
    if (fabs(val) >= eps)
        macierz_sasiedztwa[x][y]= val;
}

bool gauss0(map<int, map<int, double>> &AB, vector<double> &X)
{
    int i,j,k,n;
    double m,s;
    n=X.size(); // ilosc wierszy

    // usuwanie zer z przekatnej
    //for(i = 0; i < n - 1; i++)
    //{
    //  if(abs(AB[i][i]) < eps) // 0
    //  {
    //      for(j = 0; j < n - 1; j++)
    //      {
    //          if (j==i)
    //              continue;
    //          if (AB[j][i] >= eps && AB[i][j] >= eps)
    //          {
    //              vector<double> tmp = AB[i];
    //              AB[i] = AB[j];
    //              AB[j] = tmp;
    //              i = 0;
    //          }
    //      }
    //  }
    //}


    // eliminacja
    for(i = 0; i < n - 1; i++)
    {
        for(j = i + 1; j < n; j++)
        {
            // zero na przekatnej
            //if(fabs(AB[i][i]) < eps) return false;
            if(fabs(getXY(AB, i,i)) < eps) return false;

            //m = -AB[j][i] / AB[i][i];
            m = -getXY(AB, j, i) / getXY(AB, i,i);

            for(k = i + 1; k <= n; k++)
                //AB[j][k] += m * AB[i][k];
                setXY(AB, j, k, getXY(AB, j, k) + (m*getXY(AB, i, k)));
        }
    }

    // wyliczanie niewiadomych
    for(i = n - 1; i >= 0; i--)
    {
        //s = AB[i][n];
        s = getXY(AB, i, n);

        for(j = n - 1; j >= i + 1; j--)
            //s -= AB[i][j] * X[j];
            s -= getXY(AB, i, j) * X[j];
        // zero na przekatnej
        //if(fabs(AB[i][i]) < eps) return false;
        if(fabs( getXY(AB, i, i) ) < eps) return false;
        X[i] = s / getXY(AB, i, i);
    }
    return true;
}

bool gauss(vector <vector<double>> &AB, vector<double> &X)
{
    int i,j,k,n;
    double m,s;
    n=AB.size(); // ilosc wierszy

    // usuwanie zer z przekatnej
    for(i = 0; i < n - 1; i++)
    {
        if(abs(AB[i][i]) < eps) // 0
        {
            for(j = 0; j < n - 1; j++)
            {
                if (j==i)
                    continue;
                if (AB[j][i] >= eps && AB[i][j] >= eps)
                {
                    vector<double> tmp = AB[i];
                    AB[i] = AB[j];
                    AB[j] = tmp;
                    i = 0;
                }
            }
        }
    }


    // eliminacja
    for(i = 0; i < n - 1; i++)
    {
        for(j = i + 1; j < n; j++)
        {
            // zero na przekatnej
            if(fabs(AB[i][i]) < eps) return false;
            m = -AB[j][i] / AB[i][i];
            for(k = i + 1; k <= n; k++)
                AB[j][k] += m * AB[i][k];
        }
    }

    // wyliczanie niewiadomych
    for(i = n - 1; i >= 0; i--)
    {
        s = AB[i][n];
        for(j = n - 1; j >= i + 1; j--)
            s -= AB[i][j] * X[j];
        // zero na przekatnej
        if(fabs(AB[i][i]) < eps) return false;
        X[i] = s / AB[i][i];
    }
    return true;
}


bool wczytaj0(map<int, int> &mapa , vector <double> &ilosc, map<int, map<int, double>> &macierz_sasiedztwa)
{
    int currId = 0;
    int src, dst;
    int count = 0;

    while (!cin.eof())
    {
        cin >> src >> dst;
        if (cin.eof())
            break;


        if (src > count)
            count = src;
        if (dst > count)
            count = dst;
        while(ilosc.size() <= count)
            ilosc.push_back( 0 );
        ilosc[src]++;

        setXY(macierz_sasiedztwa, dst, src, 1);
    }

    return true;
}


bool wczytaj1()
{
    std::multimap<unsigned int, unsigned int> pairs;

    unsigned int left, right, max=0;
    while (std::cin >> left >> right)
    {
        if (max < left)
        {
            max = left;
        }
        if (max < right)
        {
            max = right;
        }
        pairs.insert( pair<unsigned int,unsigned int> (left, right) );

    }

    //return pairs;
    return true;
}

bool wczytaj(vector <double> &ilosc, vector< vector<double> > &macierz_sasiedztwa)
{
    int currId = 0;

    int src, dst;
    int count = 0;
    while (!cin.eof())
    {
        int idSrc, idDst;

        cin >> src >> dst;
        if (cin.eof() || src == -1)
            break;

        /* powiekszanie wektorow*/

        if (src > count)
            count = src;
        if (dst > count)
            count = dst;
        while(ilosc.size() <= count)
            ilosc.push_back( 0 );
        while(macierz_sasiedztwa.size() <= count)
        {
            macierz_sasiedztwa.push_back(vector<double>());
        }
        for(int i=0; i<macierz_sasiedztwa.size(); i++)
        {
            while (macierz_sasiedztwa[i].size() <= count)
            {
                macierz_sasiedztwa[i].push_back( 0 );
            }
        }


        ilosc[src]++;
        macierz_sasiedztwa[dst][src] = 1;

    }

    return true;
}




void wypisz_macierz(vector< vector<double> > &sasiedztwo)
{
    for(int i=0; i<sasiedztwo.size(); i++)
    {
        for(int j=0; j<sasiedztwo[i].size(); j++)
        {
            cout << sasiedztwo[i][j] << "\t";
        }
        cout << endl;
    }
}

void wypisz_macierz0(vector<double> &ilosc, map<int, map<int, double>> &sasiedztwo)
{
    for(int i=0; i<ilosc.size(); i++)
    {
        for(int j=0; j<ilosc.size()+1; j++)
        {
            //cout << getxsasiedztwo[i][j] << "\t";
            cout << getXY(sasiedztwo, i, j) << "\t";
        }
        cout << endl;
    }
}

vector <vector<double>> do_wektora(vector<double> &ilosc, map<int, map<int, double>> &sasiedztwo)
{
    vector <vector<double>>  ret;
    vector<double> wers;
    for(int i=0; i<ilosc.size(); i++)
    {
        wers.clear();
        ret.push_back(wers);
        for(int j=0; j<ilosc.size()+1; j++)
        {
            ret[i].push_back(getXY(sasiedztwo, i, j) );
        }
        cout << endl;
    }

    return ret;
}

void pomnoz_razy_macierz_diagonalna0(vector<double> &ilosc, map<int, map<int, double>>  &sasiedztwo)
{

    for(int i=0; i<ilosc.size(); i++)
    {
        // dodanie krawedzi do wszystkich
        if (!(ilosc[i] > 0))
        {
            ilosc[i] = ilosc.size()-1;
            for (int j=0; j<ilosc.size(); j++)
            {
                if (i==j)
                    continue;
                //sasiedztwo[j][i] = 1;
                setXY(sasiedztwo, j, i, 1);
            }
        }

        for(int j=0; j<ilosc.size(); j++)
        {
            //sasiedztwo[j][i] *= d/ilosc[i];
            setXY(sasiedztwo, j, i, (getXY(sasiedztwo, j, i) * d)/ilosc[i]);
        }
    }
}


void pomnoz_razy_macierz_diagonalna(vector<double> &ilosc, vector< vector<double> > &sasiedztwo)
{

    for(int i=0; i<ilosc.size(); i++)
    {
        // dodanie krawedzi do wszystkich
        if (!(ilosc[i] > 0))
        {
            ilosc[i] = sasiedztwo[i].size()-1;
            for (int j=0; j<sasiedztwo[i].size(); j++)
            {
                if (i==j)
                    continue;
                sasiedztwo[j][i] = 1;
            }
        }

        for(int j=0; j<sasiedztwo[i].size(); j++)
        {
            sasiedztwo[j][i] *= d/ilosc[i];
        }
    }
}

void dodaj_kolumne(vector< vector<double> > &sasiedztwo)
{
    for(int i=0; i<sasiedztwo.size(); i++)
    {
        sasiedztwo[i].push_back( (1.0-d) / double(sasiedztwo.size()) );
    }
}

void dodaj_kolumne0(vector<double> &ilosc, map<int, map<int, double>> &sasiedztwo)
{
    for(int i=0; i<ilosc.size(); i++)
    {
        //sasiedztwo[i].push_back( (1.0-d) / double(sasiedztwo.size()) );
        setXY(sasiedztwo, i, ilosc.size(),  (1.0-d) / double(ilosc.size()));
    }
}


void I_odj_macierz(vector< vector<double> > &sasiedztwo)
{
    for(int i=0; i<sasiedztwo.size(); i++)
    {
        for(int j=0; j<sasiedztwo[i].size(); j++)
        {
            sasiedztwo[i][j] = 0-sasiedztwo[i][j];
            sasiedztwo[i][j] += i==j;
        }
    }
}

void I_odj_macierz0(vector<double> &ilosc, map<int, map<int, double>> &sasiedztwo)
{
    for(int i=0; i<ilosc.size(); i++)
    {
        for(int j=0; j<ilosc.size(); j++)
        {
            //sasiedztwo[i][j] = 0-sasiedztwo[i][j];
            setXY(sasiedztwo, i, j, 0-getXY(sasiedztwo, i, j));

            //sasiedztwo[i][j] += i==j;
            setXY(sasiedztwo, i, j, getXY(sasiedztwo, i, j) + i==j);

        }
    }
}

int main()
{


    vector<double> ilosc2;
    vector< vector<double> > sasiedztwo;


    vector<double> ilosc;
    map<int, map<int, double>> macierz_sasiedztwa;
    map<int, int> mapa;

    wczytaj(ilosc2, sasiedztwo);
    wczytaj0(mapa, ilosc, macierz_sasiedztwa);


    pomnoz_razy_macierz_diagonalna0(ilosc, macierz_sasiedztwa);
    pomnoz_razy_macierz_diagonalna(ilosc2, sasiedztwo);



    I_odj_macierz0(ilosc, macierz_sasiedztwa);
    I_odj_macierz(sasiedztwo);

    wypisz_macierz(sasiedztwo);
    wypisz_macierz0(ilosc, macierz_sasiedztwa);

    dodaj_kolumne0(ilosc, macierz_sasiedztwa);

    //wypisz_macierz0(ilosc, macierz_sasiedztwa);

    vector<vector<double>> AB= do_wektora(ilosc, macierz_sasiedztwa);
    //wypisz_macierz(AB);

    vector<double> X;
    for(int i=0; i<macierz_sasiedztwa.size(); i++)
        X.push_back( 0 );

    vector<double> Y;
    for(int i=0; i<macierz_sasiedztwa.size(); i++)
        Y.push_back( 0 );


    bool done;
    done = gauss0(macierz_sasiedztwa, X);

    done = gauss(AB, Y);

    int abc = 0;


    //vector<double> wers;
    //vector<vector<double>> AB;
    //wers.push_back(0);
    //wers.push_back(1);
    //wers.push_back(2);

    //wers.push_back(1);
    //AB.push_back(wers);
    //wers.clear();

    //wers.push_back(1);
    //wers.push_back(0);
    //wers.push_back(3);

    //wers.push_back(1);
    //AB.push_back(wers);
    //wers.clear();

    //wers.push_back(1);
    //wers.push_back(1);
    //wers.push_back(1);

    //wers.push_back(1);
    //AB.push_back(wers);
    //wers.clear();

    //bool done;
    //done = gauss(AB, X);





    return 0;
}