#ifndef LOCAL
#include <bits/allocator.h>
#pragma GCC optimize("O3,unroll-loops,no-stack-protector")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt,tune=native")
#else
#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ull = unsigned long long;
using i128 = __int128_t;

#define all(x) (x).begin(), (x).end()

const int MAX_N = 2000;

vector<int> graph[MAX_N], rev_graph[MAX_N];
bool used[MAX_N];
int color[MAX_N];
int n, m, gr;

void get_top_sort(int v, vector<int> &top_sort) {
    if (used[v]) return;
    used[v] = true;
    for (int x : graph[v]) {
        get_top_sort(x, top_sort);
    }
    top_sort.push_back(v);
}

void paint(int v, int c) {
    if (color[v] != -1) return;
    color[v] = c;
    for (int x : graph[v]) {
        paint(x, c);
    }
}

void reverse_edges() {
    for (int i = 0; i < n; ++i) {
        for (int x : graph[i]) {
            rev_graph[x].push_back(i);
        }
    }
    for (int i = 0; i < n; ++i) {
        swap(graph[i], rev_graph[i]);
        rev_graph[i].resize(0);
    }
}

int get_components() {
    reverse_edges();
    vector<int> top_sort;
    for (int i = 0; i < n; ++i) {
        get_top_sort(i, top_sort);
    }
    memset(color, -1, sizeof(color));
    int c = 0;
    for (int x : top_sort) {
        if (color[x] == -1) {
            paint(x, c++);
        }
    }
    reverse_edges();
    return c;
}

const int MOD = 1e9 + 7;

struct Modular {
    int x;

    Modular(int x = 0) : x(x) {}

    friend Modular operator+(Modular a, Modular b) {
        int res = a.x + b.x;
        return {res - (MOD & -(res >= MOD))};
    }

    friend Modular operator-(Modular a, Modular b) {
        int res = a.x - b.x;
        return {res + (MOD & -(res < 0))};
    }

    friend Modular operator*(Modular a, Modular b) {
        return int(ll(a.x) * b.x % MOD);
    }

    friend Modular operator+=(Modular &a, Modular b) {
        return a = a + b;
    }

    friend Modular operator-=(Modular &a, Modular b) {
        return a = a - b;
    }

    friend Modular operator*=(Modular &a, Modular b) {
        return a = a * b;
    }
};

vector<int> comp_vertices[MAX_N];
vector<int> incomp_graph[MAX_N];
int in_cnt[MAX_N], out_cnt[MAX_N], in_cnt_old[MAX_N], out_cnt_old[MAX_N];

void solve() {
    cin >> n >> m >> gr;
    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        --a, --b;
        graph[a].push_back(b);
    }
//    int comp_cnt = get_components();
    int comp_cnt = 1;
    int max_del_cnt = 0;
    Modular options_cnt;
    // Only leave a tree
//    map<pair<int, int>, int> intercomp_edges_cnt;
    for (int i = 0; i < n; ++i) {
        for (int x : graph[i]) {
            if (color[i] != color[x]) {
                max_del_cnt += 1;
//                intercomp_edges_cnt[make_pair(i, x)]++;
            }
        }
    }
//    for (auto [a, b] : intercomp_edges_cnt) {
//
//    }
    max_del_cnt -= comp_cnt - 1;
    for (int i = 0; i < n; ++i) {
        comp_vertices[color[i]].push_back(i);
        for (int x : graph[i]) {
            if (color[i] == color[x]) {
                incomp_graph[i].push_back(x);
                out_cnt[i]++;
                in_cnt[x]++;
                out_cnt_old[i]++;
                in_cnt_old[x]++;
            }
        }
    }
    for (int c = 0; c < comp_cnt; ++c) {
        int removable_edges = 0;
        for (int i = 0; i < (int) comp_vertices[c].size() * 2 + 10; ++i) {
            for (int v : comp_vertices[c]) {
                for (int x : incomp_graph[v]) {
                    if (out_cnt[v] == 1 && out_cnt_old[v] == 1 && in_cnt[v] > 0 ||
                        in_cnt[x] == 1 && in_cnt_old[x] == 1 && out_cnt[x] > 0) {
                        removable_edges++;
                        cout << "DELETED " << v + 1 << " " << x + 1 << "\n";
                        out_cnt[v]--;
                        in_cnt[x]--;
                    }
                }
            }
        }
        if (removable_edges == 0) {
            continue;
        }
//        removable_edges--;
        max_del_cnt += removable_edges;
        options_cnt *= removable_edges + 1;
    }
    cout << max_del_cnt << "\n";
    cout << options_cnt.x << "\n";
}

int main() {
#ifndef LOCAL
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
#endif
    int t = 1;
//    cin >> t;
    while (t--) {
        solve();
    }
}