def parse(inFile):
    [P, W] = inFile.getInts()
    wormholes = [[int(num) for num in word.split(",")] for word in inFile.getWords()]
    return (P,wormholes)

class Queue:
    def __init__(self, x):
        self.q = x
        self.qat = 0
        self.qlen = len(x)
    
    def pop(self):
        self.qat += 1
        return self.q[self.qat - 1]
    
    def elements(self):
        while (not self.empty()):
            yield self.pop()

    def push(self, x):
        self.q.append(x)
        self.qlen += 1

    def empty(self):
        return self.qat == self.qlen

def solve((numPlanets, wormholes)):
    print "There are %d planets." % numPlanets
    nbs = [[] for i in xrange(numPlanets)]
    adj = [[False for i in xrange(numPlanets)] for j in xrange(numPlanets)]
    for i in xrange(len(wormholes)):
        [p0,p1] = wormholes[i]
        adj[p0][p1] = True
        adj[p1][p0] = True
        nbs[p0].append([p1,i])
        nbs[p1].append([p0,i])
    d0 = [numPlanets+1] * numPlanets
    d0[0] = 0
    q = Queue([0])
    while (not (q.empty())):
        qi = q.pop()
        for nb in [z[0] for z in nbs[qi]]:
            if (d0[nb] > d0[qi] + 1):
                d0[nb] = d0[qi] + 1
                q.push(nb)
    d1 = [numPlanets+1] * numPlanets
    d1[1] = 0
    q = Queue([1])
    while (not (q.empty())):
        qi = q.pop()
        for nb in [z[0] for z in nbs[qi]]:
            if (d1[nb] > d1[qi] + 1):
                d1[nb] = d1[qi] + 1
                q.push(nb)
    
    threats = [[-1,-1,-1] for w in wormholes]
    n0 = len(nbs[0])
    q = Queue([])
    for i in nbs[0]:
        [j,w] = i
        if d1[j] == d1[0] - 1:
            threats[w] = [j,0,n0+len([k for k in nbs[j] if not adj[0][k[0]]])]
            q.push(w)
    rec = 0
    if d0[1] == 1:
        rec = n0 + 1
    for qi in q.elements():
        [j,i,t] = threats[qi]
        for p in nbs[j]:
            [dest,num] = p
            if (dest == 1):
                rec = max(rec, t)
            if (d0[dest] == d0[j] + 1) and (d1[dest] == d1[j] - 1):
                if threats[num][0] == -1:
                    q.push(num)
                threats[num] = max(threats[num], [dest,j,t+len([k for k in nbs[dest] if not (adj[i][k[0]] or adj[j][k[0]])])])
    return " ".join([str(d0[1] - 1),str(rec-d0[1])])

if __name__ == "__main__":
    from GCJ import GCJ
    GCJ(parse, solve, "/Users/lpebody/gcj/2011_round2/", "d").run()