POI23 Niebanalne podróże (nie)

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

const int mod = 1e9 + 7;
const int maxn = 500010;
const int maxm = 1000010;

int n, m;
vector<int> adj[maxn];

const int NOT_FOUND = -1, STOPSTOPSTOP = -2;
int bcc_size;
int bcc_sum;
int last[maxn];
int degree[maxn];

int timer;
int tin[maxn], low[maxn];
vector<pii> stk;

vector<int> adj2[maxn];

bool dfs1(int u, int p, int s2) {
    if (u == s2) return true;
    for (int v : adj2[u]) {
        if (v != p) {
            return dfs1(v, u, s2);
        }
    }
    return false;
}

int dfs2(int u, int p, int s1, int s2, int d) {
    if (u == s2) return d;
    if (u == s1) return STOPSTOPSTOP;
    for (int v : adj2[u]) {
        if (v != p) {
            return dfs2(v, u, s1, s2, d+1);
        }
    }
    return STOPSTOPSTOP;
}

void bcc_solve(int fnd1, int fnd2) {
    /*
    CASE 0:
    just a single edge (doesn't count, skip)

    CASE 1:
    normal cycle

    CASE 2:
    "onion" shape
    the graph looks like an onion with many layers
    2 nodes have same degree (>2)
    all other have degree 2
    each layer is 1 or more nodes
    each layer connects the 2 nodes with the big degree

    3 layers:
        o - o - o
      /           \
    o - o - o - o - o
      \           /
        o - o - o
    */
    static int calls = 0;
    ++calls;
    vector<int> nodes;
    int num_edges = 0, num_nodes = 0, num_2 = 0;
    int special_1 = -1, special_2 = -1, special_degree_1 = -1, special_degree_2 = -2;
    // cout << "BCC (fnd1=" << fnd1 << ", fnd2=" << fnd2 << ")\n";
    while (true) {
        int u = stk.back().first, v = stk.back().second;
        for (int k : vector<int>({u, v})) {
            nodes.push_back(k);
            if (last[k] < calls) {
                ++num_nodes;
                last[k] = calls;
                degree[k] = 1;
                // cout << "node: " << k << "\n";
            } else {
                ++degree[k];
                if (degree[k] == 2) { // 1 -> 2
                    ++num_2;
                } else if (degree[k] == 3) { // 2 -> 3+
                    --num_2;
                    if (special_1 == -1) {
                        special_1 = k;
                        special_degree_1 = 3;
                    } else if (special_2 == -1) {
                        special_2 = k;
                        special_degree_2 = 3;
                    } else {
                        // too many
                        // cout << "(too many special)\n";
                        bcc_size = STOPSTOPSTOP;
                        return;
                    }
                } else if (degree[k] > 3) {
                    if (k == special_1) {
                        ++special_degree_1;
                    } else {
                        ++special_degree_2;
                    }
                }
            }
        }
        // cout << "edge: " << u << "-" << v << "\n";
        ++num_edges;
        adj2[u].push_back(v);
        adj2[v].push_back(u);
        stk.pop_back();
        if (stk.empty() || (u == fnd1 && v == fnd2)) {
            break;
        }
    }
    // debug(num_edges, num_nodes);
    if (num_edges == 1) {
        // case 0
    } else if (num_edges == num_nodes) {
        // case 1
        if (num_2 != num_nodes || (bcc_size != NOT_FOUND && bcc_size != num_nodes)) {
            bcc_size = STOPSTOPSTOP;
        } else {
            int src = nodes[0];
            if (dfs1(adj2[src][0], -1, adj2[src][1])) {
                bcc_size = num_nodes;
                bcc_sum = (bcc_sum + num_nodes*2) % mod;
            } else {
                bcc_size = STOPSTOPSTOP;
            }
        }
    } else {
        // case 2 (onion)
        // debug(num_2, special_1, special_2);
        // debug(special_degree_1, special_degree_2);
        if (special_degree_1 != special_degree_2 || num_2 + 2 != num_nodes) {
            // cout << "stop1\n";
            bcc_size = STOPSTOPSTOP;
        } else {
            int layers = special_degree_1;
            int length = -1;
            for (int v : adj2[special_1]) {
                int length_here = dfs2(v, special_1, special_1, special_2, 1);
                if (length_here == STOPSTOPSTOP || (length != -1 && length != length_here)) {
                    bcc_size = STOPSTOPSTOP;
                    break;
                }
                length = length_here;
            }
            length = length*2;
            // debug(length);
            if (bcc_size != STOPSTOPSTOP && (bcc_size == NOT_FOUND || bcc_size == length)) {
                bcc_size = length;
                bcc_sum = (bcc_sum + (ll(layers)*(layers-1)) % mod) % mod;
            } else {
                bcc_size = STOPSTOPSTOP;
            }
        }
    }
    for (int u : nodes) {
        adj2[u].clear();
    }
}

void bcc_dfs(int u, int p) {
    tin[u] = low[u] = timer++;
    int children = 0;
    for (int v : adj[u]) {
        if (v == p) {
            continue;
        } else if (tin[v] != -1) {
            low[u] = min(low[u], tin[v]);
            if (tin[v] < tin[u]) {
                stk.emplace_back(u, v);
            }
        } else {
            ++children;
            stk.emplace_back(u, v);
            bcc_dfs(v, u);
            if (bcc_size == STOPSTOPSTOP) {
                return;
            }
            low[u] = min(low[u], low[v]);
            // the following line guarantees that we will find all BCC
            if (p == -1 || (p != -1 && low[v] >= tin[u])) {
                bcc_solve(u, v);
                if (bcc_size == STOPSTOPSTOP) {
                    return;
                }
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    bcc_size = NOT_FOUND;
    bcc_sum = 0;
    timer = 0;
    memset(tin, -1, sizeof(tin));
    bcc_dfs(1, -1);
    if (bcc_size == NOT_FOUND) {
        cout << "BRAK\n";
    } else if (bcc_size == STOPSTOPSTOP) {
        cout << "NIE\n";
    } else {
        cout << "TAK\n" << bcc_size << " " << bcc_sum << "\n";
    }
}