Дан ориентированный граф \(G\) с \(n\) вершинами и \(m\) ребрами.
Изначально граф \(H\) совпадает с графом \(G\). Затем вы решили выполнить следующие действия:
- Если в графе \(H\) существует тройка вершин \(a\), \(b\), \(c\) такая, что есть ребро из \(a\) в \(b\) и ребро из \(b\) в \(c\), но нет ребра из \(a\) в \(c\), то добавить ребро из \(a\) в \(c\).
- Повторять предыдущий шаг до тех пор, пока существуют такие тройки.
Заметим, что после выполнения этих действий количество ребер в \(H\) может достигать \(n^2\).
Вы также записали некоторые значения на вершинах графа \(H\): на вершине \(i\) записано значение \(a_i\).
Рассмотрим простой путь, состоящий из \(k\) различных вершин с номерами \(v_1, v_2, \ldots, v_k\). Длина такого пути равняется \(k\). Значение этого пути определим как \(\sum_{i = 1}^k a_{v_i}\).
Простой путь считается самым длинным, если в графе нет другого простого пути с большей длиной.
Среди всех самых длинных простых путей в \(H\) найдите тот, который имеет наименьшее значение.
Выходные данные
Для каждого набора входных данных выведите два числа — длину самого длинного простого пути в \(H\) и минимально возможное значение такого пути.
Примечание
В первом наборе входных данных самый длинный путь в обоих графах равен \(1 \to 3 \to 4 \to 5 \to 2\). Поскольку путь включает все вершины, то минимально возможное значение самого длинного пути равно сумме значений по всем вершинам, которое равняется \(12\).
Во втором наборе входных данных самый длинный путь равен \(1 \to 2 \to 3 \to 4 \to 6 \to 7\). Поскольку самых длинных путей с вершиной \(5\) не существует, то такой путь имеет минимально возможное значение \(5\,999\,999\,995\).
В третьем наборе входных данных можно доказать, что не существует пути длиннее \(11\) и что значение самого длинного пути не может быть меньше \(37\). Также заметим, что данный граф содержит петли и кратные ребра.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
5 6
2 2 4 1 3
1 2
1 3
2 4
3 4
4 5
5 2
7 7
999999999 999999999 999999999 999999999 1000000000 999999999 1000000000
1 2
2 3
3 4
4 1
4 5
4 6
6 7
14 22
2 3 5 7 3 4 1 4 3 4 2 2 5 1
1 2
2 3
2 4
3 1
4 4
4 5
5 6
5 6
5 12
6 7
6 8
7 5
7 7
7 9
8 4
9 11
10 9
11 10
11 10
12 13
13 14
14 12
|
5 12
6 5999999995
11 37
|