#include <vector>
#include <iostream>
#include <map>
#include <list>
#include <time.h>
#include <assert.h>

using namespace std;

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

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 wczytaj(map<int, int> &backNodes, vector <double> &ilosc, vector< vector<double> > &macierz_sasiedztwa)
{
    int currId = 0;

    int src, dst;
    int count = 0;

    map<int, int> Nodes;

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

        // mapy id
        if (Nodes.find(src) == Nodes.end())
        {
            Nodes[src] = currId;
            backNodes[currId] = src;
            currId++;
        }
        if (Nodes.find(dst) == Nodes.end())
        {
            Nodes[dst] = currId;
            backNodes[currId] = dst;
            currId++;
        }

        /* powiekszanie wektorow*/
        if (Nodes[src] > count)
            count = Nodes[src];
        if (Nodes[dst] > count)
            count = Nodes[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 );
            }
        }

        // ustawienie macierzy
        ilosc[Nodes[src]]++;
        macierz_sasiedztwa[Nodes[dst]][Nodes[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 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 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 wczytaj_uklad(vector< vector<double> > &sasiedztwo)
{
    // 0 1 1  1
    // 1 0 1  1
    // 1 1 1  1

    vector<double> wiersz;

    wiersz.clear();
    wiersz.push_back ( 0 );
    wiersz.push_back ( 1 );
    wiersz.push_back ( 1 );
    wiersz.push_back ( 1 );
    sasiedztwo.push_back(wiersz);

    wiersz.clear();
    wiersz.push_back ( 1 );
    wiersz.push_back ( 0 );
    wiersz.push_back ( 1 );
    wiersz.push_back ( 1 );
    sasiedztwo.push_back(wiersz);

    wiersz.clear();
    wiersz.push_back ( 1 );
    wiersz.push_back ( 1 );
    wiersz.push_back ( 1 );
    wiersz.push_back ( 1 );

    sasiedztwo.push_back(wiersz);
}

void wczytaj_uklad2(vector< vector<double> > &sasiedztwo)
{
    // 1 0 1  1
    // 0 1 1  1
    // 1 0 1  1

    vector<double> wiersz;

    wiersz.clear();
    wiersz.push_back ( 1 );
    wiersz.push_back ( 0 );
    wiersz.push_back ( 1 );
    wiersz.push_back ( 1 );
    sasiedztwo.push_back(wiersz);

    wiersz.clear();
    wiersz.push_back ( 0 );
    wiersz.push_back ( 1 );
    wiersz.push_back ( 1 );
    wiersz.push_back ( 1 );
    sasiedztwo.push_back(wiersz);

    wiersz.clear();
    wiersz.push_back ( 1 );
    wiersz.push_back ( 0 );
    wiersz.push_back ( 1 );
    wiersz.push_back ( 1 );

    sasiedztwo.push_back(wiersz);
}


//#define WLASNA

int main()
{
    vector< vector<double> > sasiedztwo;
    vector<double> ilosc;
    map<int, int> Nodes;

#ifndef WLASNA
    wczytaj(Nodes, ilosc, sasiedztwo);
#endif
#ifdef WLASNA
    wczytaj_uklad(sasiedztwo); // wczytanie wlasnego ukl rownan
#endif

    time_t now;
    time(&now);

#ifndef WLASNA
    pomnoz_razy_macierz_diagonalna(ilosc, sasiedztwo);
    I_odj_macierz(sasiedztwo);
#endif

    dodaj_kolumne(sasiedztwo);

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

    bool done;
    done = gauss( sasiedztwo, Y);

    time_t seconds = time(NULL) - now;

    assert(done);
#ifndef WLASNA
    if (done)
    {
        double sumRank = 0;
        for(int i=0; i<Y.size(); i++)
        {
            cout << Nodes[i] << "\trank:\t" << Y[i] << endl;
            sumRank += Y[i];
        }

        cout << "nodes: " << Y.size() << endl;
        cout << "rank sum: " << sumRank << endl;
        cout << "seconds: " << seconds << endl;
    }
#endif

    return 0;
}