Четвірко- та сімкоподібні щасливі графи
Limits: 2 sec., 256 MiB
Назвемо граф четвіркоподібним, якщо він ізоморфний графові на рис. 1.
Назвемо граф сімкоподібним, якщо він ізоморфний графові на рис. 2.
Марічці подобаються четвіркоподібні графи, а Зенику — сімкоподібні.
Порахуйте кількість четвірко- та сімкоподібних підграфів заданого графу.
Граф \(G'=(V', E')\) — підграф \(G=(V, E)\), якщо \(V' \subseteq V\) та \(E' \subseteq E\).
Input
У першому рядку задано два цілих числа \(n\) і \(m\) — кількості вершин і ребер графу.
У наступних \(m\) рядках задано по два цілих числа \(u_i\), \(v_i\) — номери вершин, з’єднаних ребром.
Output
В одному рядку виведіть два цілих числа — кількості четвірко- та сімкоподібних підграфів заданого графу.
Constraints
\(1 \le n \le 2 \cdot 10^5\),
\(0 \le m \le 2 \cdot 10^5\),
граф не містить петель і мультиребер.
Samples
Input (stdin) | Output (stdout) |
---|---|
10 10 7 3 2 7 1 10 1 5 3 8 7 1 9 5 6 3 2 4 4 1 | 20 19 |
Notes
Деякі четвіркоподібні підграфи:
граф з вершинами 1, 4, 5, 9, 10 і ребрами \(\{1, 4\}\), \(\{1, 5\}\), \(\{1, 10\}\), \(\{5, 9\}\);
граф з вершинами 2, 3, 6, 7, 8 і ребрами \(\{2, 7\}\), \(\{3, 6\}\), \(\{3, 7\}\), \(\{3, 8\}\).
Деякі сімкоподібні підграфи:
граф з вершинами 2, 3, 4, 7 і ребрами \(\{2, 4\}\), \(\{2, 7\}\), \(\{3, 7\}\);
граф з вершинами 1, 5, 7, 9 і ребрами \(\{1, 5\}\), \(\{1, 7\}\), \(\{5, 9\}\).
Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
---|