コード
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Scanner;
public class Main {
private HashSet<Integer> black, white;
public void solve() {
Scanner scanner = new Scanner(System.in);
int N = scanner.nextInt();
int M = scanner.nextInt();
ArrayList<ArrayList<Integer>> graph = new ArrayList<>(N);
for (int i = 0; i < N; i++) {
graph.add(new ArrayList<Integer>());
}
for (int i = 0; i < M; i++) {
int x = scanner.nextInt() - 1;
int y = scanner.nextInt() - 1;
graph.get(x).add(y);
graph.get(y).add(x);
}
scanner.close();
if (M == 0) {
System.out.println("3 " + ((long) N * (N - 1) * (N - 2) / 6));
return;
}
for (int i = 0; i < N; i++) {
if (graph.get(i).size() >= 2) {
break;
}
if (i == N - 1) {
System.out.println("2 " + ((long) M * (N - 2)));
return;
}
}
long ans = 0;
int[] color = new int[N];
black = new HashSet<>();
white = new HashSet<>();
for (int i = 0; i < N; i++) {
if (color[i] == 0) {
black.clear();
white.clear();
if (!colorDFS(i, 1, color, graph)) {
System.out.println("0 1");
return;
}
long b = black.size();
long w = white.size();
ans += b * (b - 1) / 2;
ans += w * (w - 1) / 2;
}
}
System.out.println("1 " + ans);
}
private boolean colorDFS(int v1, int c, int[] color, ArrayList<ArrayList<Integer>> graph) {
color[v1] = c;
if (c > 0) {
black.add(v1);
} else {
white.add(v1);
}
for (int v2 : graph.get(v1)) {
if (color[v2] == c) {
return false;
}
if (color[v2] == -c) {
continue;
}
if (!colorDFS(v2, -c, color, graph)) {
return false;
}
}
return true;
}
public static void main(String[] args) {
new Main().solve();
}
}