#include<iostream>
#include<fstream>
#include<iomanip>
using namespace std;

struct Edge {
    int vertex;
    int adjacency;
    Edge* next;
    Edge()
    {
        next = NULL;
    }
};
void creation(Edge*&head, ifstream &input) {
    Edge*current = head;
    input >> head->vertex >> head->adjacency;
    while (!input.eof())
    {
        current->next = new Edge;
        current = current->next;
        input >> current->vertex >> current->adjacency;
    }
}
int the_number_of_vertices(Edge*&head) {
    Edge* current = head;
    int max = head->vertex;
    while (current)
    {
        if (max < current->vertex)
        {
            max = current->vertex;
        }
        current = current->next;
    }
    return max;
}
int the_number_of_pairs_of_numbers(Edge*&head) {
    Edge* current = head;
    int amount = 0;
    while (current)
    {
        ++amount;
        current = current->next;
    }
    return amount;
}
void amount_of_neighbourhood(Edge*head, int *array_of_adjacency) {
    Edge*current = head;
    while (current)
    {
        ++array_of_adjacency[current->vertex];
        current = current->next;
    }
}
void creaction_array_of_adjacency(Edge*head, int *array_of_adjacency, int &size_of_array, int amount_of_edges) {
    Edge*current = head;
    int position = size_of_array - amount_of_edges;
    for (int i = 0; i < size_of_array - amount_of_edges; ++i) {
        if (array_of_adjacency[i] != 0) {
            array_of_adjacency[i] = position;
            current = head;
            while (current) {
                if (current->vertex == i) {
                    array_of_adjacency[position] = current->adjacency;
                    ++position;
                }
                current = current->next;
            }
        }
    }
}
void print_array(int*arr, int &size_of_array) {
    for (int i = 0; i < size_of_array; ++i) {
        cout << setw(4) << i;
    }
    cout << endl;
    for (int i = 0; i < size_of_array; ++i) {
        cout << setw(4) << arr[i];
    }
    cout << endl;
}
void print_vertex_and_adjacency(int* arr, int &size_of_array, int &amount_of_edges) {
    int PrintBorder = 0;
    for (int i = 0; i < size_of_array - amount_of_edges; ++i) {
        if (arr[i] != 0) {
            PrintBorder = size_of_array;
            int j = i + 1;
            while (j < size_of_array - amount_of_edges) {
                if (arr[j] != 0) {
                    PrintBorder = arr[j];
                    break;
                }
                ++j;
            }
            cout << i << " : ";
            for (int j = arr[i]; j < PrintBorder; ++j)
            {
                cout << arr[j] << "  ";
            }
            cout << endl;
        }
    }
}
int main() {
    ifstream input("input.txt");

    Edge *Edges = new Edge;
    creation(Edges, input);
    int amount_of_edges = the_number_of_pairs_of_numbers(Edges);
    int size_of_array = the_number_of_vertices(Edges) + 1 + amount_of_edges;
    int *array_of_adjacency = new int[size_of_array];
    for (int i = 0; i < size_of_array; ++i)
    {
        array_of_adjacency[i] = 0;
    }
    amount_of_neighbourhood(Edges, array_of_adjacency);
    creaction_array_of_adjacency(Edges, array_of_adjacency, size_of_array, amount_of_edges);
    print_array(array_of_adjacency, size_of_array);
    print_vertex_and_adjacency(array_of_adjacency, size_of_array, amount_of_edges);
    system("pause");
    return 0;
}