#include <vector>
#include <iostream>
#include <map>
#include <list>
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;

}

double getXYRazyMacierzDiag(vector <double> &ilosc, map<int, map<int, double>> &macierz_sasiedztwa, int x, int y)
{
    if (y>=ilosc.size())
        return getXY(macierz_sasiedztwa, x, y);


    double ret = 0;
    if ((macierz_sasiedztwa.find(x) != macierz_sasiedztwa.end())
        && (macierz_sasiedztwa[x].find(y) != macierz_sasiedztwa[x].end()) )
    {
        // jezeli jest polaczenie
        ret = ret - macierz_sasiedztwa[x][y];
        ret = ret * (double)d/(double)ilosc[y];
        ret = ret + (x==y ? 1.0 : 0.0);
        // return -(double)macierz_sasiedztwa[x][y] * (double)d/(double)ilosc[y] + x==y;
    }
    else
    {
        if (!(ilosc[x] > 0))
        {
                //return double(0.0-(1.0 * d/(double)ilosc.size()) + x==y);
                ret = ret - (1.0 * d/(double)ilosc.size());
                ret = ret + (double)x==y;
        }
        else
            //return double(0.0 + x==y);
            ret = (double)x==y;
    }

    return ret;

}

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

void setXYRazyMacierzDiag(vector <double> &ilosc, map<int, map<int, double>> &macierz_sasiedztwa, int x, int y, double val)
{
    if (fabs(val) < eps)
        return;


    if (y>=ilosc.size())
    {
        setXY(macierz_sasiedztwa, x, y, val);
        return;
    }

    double set;

    // jezeli jest polaczenie
    //ret = ret - macierz_sasiedztwa[x][y];
    //ret = ret * (double)d/(double)ilosc[y];
    //ret = ret + (x==y ? 1.0 : 0.0);

    set = val;
    set = set - (x==y ? 1.0 : 0.0);
    set = set / ((double)d/(double)ilosc[y]);
    macierz_sasiedztwa[x][y] = -set;


}

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

    // eliminacja
    for(i = 0; i < n - 1; i++)
    //for(map<int, map<int, double>>::iterator it=AB.begin(); it!=AB.end(); ++it)
    {
        /*if (ilosc[it->first]<1)
            continue;*/


        // musi iterowac zawsze gdy jakikolwiek element dla kazdych wierszy nie tylko dla danego
        //list<int>::iterator it3= cols.begin();
        //advance (it3, it->first);
        //for(it3 ; it3 != cols.end(); ++it3)
        for(j = i + 1; j < n; j++)
        {
            /*j = *it3;
            if (j==n || j == it->first)
                continue;*/
            // zero na przekatnej
            //if(fabs(AB[i][i]) < eps) return false;
            if(fabs(getXYRazyMacierzDiag(ilosc, AB, i,i)) < eps)
                return false;

            //m = -AB[j][i] / AB[i][i];
            m = -getXYRazyMacierzDiag(ilosc, AB, j, i) / getXYRazyMacierzDiag(ilosc, AB, i, i);
            if (fabs(m) < eps)
                continue;
            for(k = i + 1; k <= n; k++)
            //for(map<int, double>::iterator it2=it->second.begin(); it2!=it->second.end(); ++it2)
                //AB[j][k] += m * AB[i][k];
                setXYRazyMacierzDiag(ilosc, AB, j, k, getXYRazyMacierzDiag(ilosc, AB, j, k) + (m*getXYRazyMacierzDiag(ilosc, AB, i, k)));
        }
    }

    // wyliczanie niewiadomych
    for(i = n - 1; i >= 0; i--)
    {
        /*if (ilosc[i]<1)
            continue;*/

        //s = AB[i][n];
        s = getXYRazyMacierzDiag(ilosc, AB, i, n);

        for(j = n - 1; j >= i + 1; j--)
            //s -= AB[i][j] * X[j];
            s -= getXYRazyMacierzDiag(ilosc, AB, i, j) * X[j];
        // zero na przekatnej
        //if(fabs(AB[i][i]) < eps) return false;
        if(fabs( getXYRazyMacierzDiag(ilosc, AB, i, i) ) < eps) return false;
        X[i] = s / getXYRazyMacierzDiag(ilosc, 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(list<int> &cols, 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]++;
        cols.push_back(src);

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

    cols.sort();
    cols.unique();
    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_macierz1(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 << getXYRazyMacierzDiag(ilosc, 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;
    list<int> cols;

    //wczytaj(ilosc2, sasiedztwo);

    wczytaj0(cols, 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);


    dodaj_kolumne0(ilosc, macierz_sasiedztwa);

    //dodaj_kolumne(sasiedztwo);


    /*wypisz_macierz(sasiedztwo);
    cout << endl;
    wypisz_macierz1(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<ilosc.size(); i++)
        Y.push_back( 0 );


    bool done;
    done = gauss0(cols, ilosc, macierz_sasiedztwa, Y);

    //wypisz_macierz(sasiedztwo);

    //done = gauss( sasiedztwo, Y);

    int abc = 0;







    return 0;
}