Вам дан турнир — полный ориентированный граф.
За одну операцию вы можете взять любую вершину \(v\) и поменять направления всех ребер с \(v\) на одном из концов (таким образом все ребра \(u \to v\) меняют направление на \(v \to u\) и наоборот).
Вам нужно сделать турнир сильно связным за минимальное количество таких операций.
А также, если это возможно, вам необходимо посчитать количество способов сделать турнир сильно связным за такое число операций (два способа отличаются, если для какого-то \(i\), вершина выбранная на \(i\)-й операции одного способа, отличается от вершины выбранной на \(i\)-й операции другого способа). Вам нужно найти остаток от деления этой величины на \(998\,244\,353\).
Выходные данные
Если невозможно сделать турнир сильно связным за такое количество операций, выведите «-1».
Иначе, выведите два целых числа: минимальное количество операций, которое нужно, чтобы сделать турнир сильно связным и количество способов сделать турнир сильно связным за такое число операций, по модулю \(998\,244\,353\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
010
001
100
|
0 1
|
|
2
|
4
0010
1000
0100
1110
|
-1
|
|
3
|
6
010000
001000
100000
111001
111100
111010
|
2 18
|