Вам дан ориентированный ациклический граф из \(n\) вершин и \(m\) ребер. Для всех ребер графа \(a \to b\) выполняется \(a < b\).
Вам нужно найти количество пар вершин \(x\), \(y\) таких, что \(x > y\), и после добавления в граф ребра \(x \to y\) в нем будет существовать гамильтонов путь.
Выходные данные
Для каждого набора входных данных выведите одно целое число: количество пар вершин \(x\), \(y\), \(x > y\), таких, что после добавления в граф ребра \(x \to y\) в графе найдется гамильтонов путь.
Примечание
В первом примере любое ребро \(x \to y\) такое, что \(x > y\), подойдет, т. к. уже существует путь \(1 \to 2 \to 3\).
Во втором примере подходит только ребро \(4 \to 1\). Если его добавить, появится путь \(3 \to 4 \to 1 \to 2\).
В третьем примере можно добавить ребра \(2 \to 1\), \(3 \to 1\), \(4 \to 1\), \(4 \to 2\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
3 2
1 2
2 3
4 3
1 2
3 4
1 4
4 4
1 3
1 4
2 3
3 4
|
3
1
4
|