import sys
import random
import heapq
from collections import deque
input = sys.stdin.readline
def fg():
    return int(input())
def fgh():
    return [int(xx) for xx in input().split()]
def tt():
    sys.stdout.flush()
def sd():
    print('Yes')
def df():
    print('No')
'''n, m, k, q = fgh()
a = fgh()
a.sort()
L = -10 ** 10
R = 10 ** 10
while R - L > 1:
    M = (L + R) // 2
    ss = 0
    for i in range(n):
        ss += max(0, min(m, a[i] - M))
    if ss >= k * m:
        L = M
    else:
        R = M
ss = 0
for i in range(n):
    ss += max(0, min(m, a[i] - L))
ss -= k * m
b = []
for i in range(n):
    b.append(a[i] - max(0, min(m, a[i] - L)))
b.sort()
for i in range(n):
    if b[i] >= L and ss > 0:
        b[i] += 1
        ss -= 1
b.sort()
print(*b)
pr = [0]
for i in range(n):
    pr.append(pr[-1] + a[i])
for __ in range(q):
    t, m, k, x = fgh()
    L = -10 ** 10
    R = 10 ** 10
    while R - L > 1:
        M = (L + R) // 2
        l1 = -1
        r1 = n
        while r1 - l1 > 1:
            m1 = (l1 + r1) // 2
            if a[m1] >= M:
                r1 = m1
            else:
                l1 = m1
        l2 = -1
        r2 = n
        while r2 - l2 > 1:
            m1 = (l2 + r2) // 2
            if a[m1] >= M + m:
                r2 = m1
            else:
                l2 = m1
        ss = m * (n - r2) + pr[r2] - pr[r1] - (r2 - r1) * M
        if ss >= m * k:
            L = M
        else:
            R = M
    M = L
    l1 = -1
    r1 = n
    while r1 - l1 > 1:
        m1 = (l1 + r1) // 2
        if a[m1] >= M:
            r1 = m1
        else:
            l1 = m1
    l2 = -1
    r2 = n
    while r2 - l2 > 1:
        m1 = (l2 + r2) // 2
        if a[m1] >= M + m:
            r2 = m1
        else:
            l2 = m1
    ss = m * (n - r2) + pr[r2] - pr[r1] - (r2 - r1) * M
    ss -= m * k
    x -= 1
    l1 = -1
    r1 = n
    while r1 - l1 > 1:
        m1 = (l1 + r1) // 2
        if a[m1] - max(0, min(m, a[m1] - M)) > M:
            r1 = m1
        else:
            l1 = m1
    if r1 - ss <= x < r1:
        print(a[x] - max(0, min(m, a[x] - M)) + 1)
    else:
        print(a[x] - max(0, min(m, a[x] - M)))'''
'''n, m = fgh()
a = fgh()
b = fgh()
c = fgh()'''
n, m, g = fgh()
a = [[] for i in range(n)]
p = []
for _ in range(m):
    u, v = fgh()
    u -= 1
    v -= 1
    p.append((u, v))
    a[u].append(v)
step = [1]
for i in range(30):
    step.append(step[-1] * 2)
good = [1] * step[m]
D = [[0] * n for i in range(n)]
for i in range(n):
    q = deque()
    q.append(i)
    v = [0] * n
    v[i] = 1
    while q:
        c = q.popleft()
        for u in a[c]:
            if v[u] == 0:
                v[u] = 1
                q.append(u)
                D[i][u] = 1
g = [[] for i in range(n)]
for i in range(n):
    for j in range(i + 1, n):
        if D[i][j] and D[j][i]:
            g[i].append(j)
            g[j].append(i)
for ii in range(1, step[m]):
    a1 = [[] for i in range(n)]
    for j in range(m):
        if ii & step[j]:
            a1[p[j][1]].append(p[j][0])
        else:
            a1[p[j][0]].append(p[j][1])
    D = [[0] * n for i in range(n)]
    for i in range(n):
        q = deque()
        q.append(i)
        v = [0] * n
        v[i] = 1
        while q:
            c = q.popleft()
            for u in a1[c]:
                if v[u] == 0:
                    v[u] = 1
                    q.append(u)
                    D[i][u] = 1
    g1 = [[] for i in range(n)]
    for i in range(n):
        for j in range(i + 1, n):
            if D[i][j] and D[j][i]:
                g1[i].append(j)
                g1[j].append(i)
    if g1 == g:
        good[ii] = 0
bt = [0] * step[m]
for i in range(step[m]):
    for j in range(m):
        if i & step[j]:
            bt[i] += 1
            good[i] &= good[i - step[j]]
ans = 0
for i in range(step[m]):
    if good[i]:
        ans = max(ans, bt[i])
ee = 0
for i in range(step[m]):
    if good[i] and bt[i] == ans:
        ee += 1
print(ans)
print(ee)