#include <iostream>
#include <vector>
#include <cstring>

bool a [ 100 ] [ 100 ] , b [ 100 ] [ 100 ];

int main ( void ) {
    int n , marime;
    std::cin >> marime >> n;
    for ( int i = 0 ; i < n ; i ++ ) {
        int z , y;
        std::cin >> z >> y;
        a [ z ] [ y ] = true;
    }

    std::memcpy ( b , a , sizeof ( a ) );

    for ( auto i = 1 ; i <= marime ; i ++ )
        for ( auto j = 1 ; j <= marime ; j ++ )
            for ( auto k = 1 ; k <= marime ; k ++ )
                if ( !a [ j ] [ k ] )
                    a [ j ] [ k ] = a [ j ] [ i ] * a [ i ] [ k ];

    std::cout << "adiacenta: \n";
    for ( auto i = 1 ; i <= marime ; i ++ ) {
        for ( auto j = 1 ; j <= marime ; j ++ )
            std::cout << b [ i ] [ j ] << " ";
        std::cout << '\n';
    }

    std::cout << "drumuri: \n";
    for ( auto i = 1 ; i <= marime ; i ++ ) {
        for ( auto j = 1 ; j <= marime ; j ++ )
            std::cout << a [ i ] [ j ] << " ";
        std::cout << '\n';
    }
}

/*
4 4
4 1 1 2 2 3 3 1
*/