#!/usr/bin/python3

from collections import deque


def build_adjacency_list(edges, n):
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
    return graph


def bfs_distances(graph, start, n):
    dist = [2*n] * n
    dist[start] = 0
    neighbors = deque([start])

    while neighbors:
        adj = neighbors.popleft()
        for adj_adj in graph[adj]:
            if dist[adj_adj] == 2*n:
                dist[adj_adj] = dist[adj] + 1
                neighbors.append(adj_adj)

    return dist


n, m = map(int, input().split())
edges = [list(map(int, input().split())) for _ in range(m)]

dists1 = bfs_distances(build_adjacency_list(edges, n), 0, n)
dists2 = bfs_distances(build_adjacency_list(map(reversed, edges), n), 0, n)
dists = [dists1[i] + dists2[i] for i in range(n)]

print(*min((y,x) for (x,y) in enumerate(dists)))