Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <algorithm>
- #include <bitset>
- #include <cmath>
- #include <cstdio>
- #include <cstring>
- #include <deque>
- #include <iomanip>
- #include <iostream>
- #include <queue>
- #include <map>
- #include <numeric>
- #include <set>
- #include <sstream>
- #include <stack>
- #include <utility>
- #include <vector>
- #define INF 1000000000
- #define FOR(i, a, b) for(int i=int(a); i<int(b); i++)
- #define FORC(cont, it) for(typeof((cont).begin()) it = (cont).begin(); it != (cont).end(); it++)
- #define pb push_back
- using namespace std;
- typedef long long ll;
- typedef pair<int, int> ii;
- typedef vector<int> vi;
- typedef vector<ii> vii;
- typedef vector<vi> vvi;
- #define maxN 100000
- bool visited[maxN], cyc[maxN];
- int visitOrder[maxN];
- ii ed[maxN];
- vi edges[maxN];
- bool findCycles(int n, int v) {
- if (cyc[n]) {
- if ((v - visitOrder[n]) & 1) {
- return true;
- }
- return false;
- }
- if (visited[n]) return false;
- visitOrder[n] = v;
- cyc[n] = true;
- visited[n] = true;
- bool ret = false;
- FOR(i, 0, edges[n].size()) {
- int id = edges[n][i];
- int next = ed[id].second;
- if (ed[id].first != n) next = ed[id].first;
- ret |= findCycles(next, v + 1);
- }
- cyc[n] = false;
- return ret;
- }
- ll sumN(ll n) {
- return n*(n + 1) / 2;
- }
- void sum(ii&l, ii r) {
- l.first += r.first;
- l.second += r.second;
- }
- ii countRB(int n, bool red) {
- ii ret = ii(0, 0);
- if (visited[n]) return ret;
- if (red) ret.first++;
- else ret.second++;
- visited[n] = true;
- FOR(i, 0, edges[n].size()) {
- int id = edges[n][i];
- sum(ret, countRB(ed[id].first, !red));
- sum(ret, countRB(ed[id].second, !red));
- }
- return ret;
- }
- int main() {
- ll n, m, a, b, minE, ways;
- while (scanf("%I64d %I64d", &n, &m)!=EOF) {
- bool vCount = false;
- FOR(i, 0, n) edges[i].clear();
- FOR(i, 0, m) {
- scanf("%I64d %I64d", &a, &b);
- a--, b--;
- ed[i] = ii(a, b);
- edges[a].push_back(i);
- edges[b].push_back(i);
- }
- memset(visited, false, sizeof(visited));
- bool cycFound = false;
- FOR(i, 0, n) {
- cycFound |= findCycles(i, 0);
- if (edges[i].size() > 1) vCount = true;
- }
- if (cycFound) {
- minE = 0;
- ways = 1;
- }
- else if (vCount) {
- minE = 1;
- ways = 0;
- memset(visited, false, sizeof(visited));
- FOR(i, 0, n) {
- if (edges[i].size()) {
- ii a = countRB(i, true);
- ways+=sumN(a.first - 1) + sumN(a.second - 1);
- }
- }
- }
- else if (m) {
- minE = 2;
- ways = m*(n - 2);
- }
- else {
- minE = 3;
- ways = 0;
- FOR(i, 2, n) {
- ways += sumN(i-1);
- }
- }
- printf("%I64d %I64d\n", minE, ways);
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement