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)]
for _ in range(m):
    u, v = fgh()
    u -= 1
    v -= 1
    a[u].append(v)
if g == 3:
    print(m - n + 1)
    print(1)
else:
    print(max(0, m - n + 1))
    print(1)