Белый кролик попал в лабиринт. Лабиринт представляет собой ориентированный граф с $n$ вершинами и $m$ ребрами, в котором могут быть кратные ребра и петли. Вершины пронумерованы от $1$ до $n$, начальная вершина — $S$, конечная — $T$. Гарантируется, что из любой вершины существует путь до $T$.
На каждом ребре лабиринта находится монстр одного из двух типов: $0$ или $1$. У белого кролика есть очки, изначально равные $0$. Каждый раз, когда кролик проходит по ребру:
- Если на ребре монстр типа $1$, кролик побеждает его, получает $1$ очко и переходит в конец этого ребра.
- Если на ребре монстр типа $0$, кролик оказывается оглушен. Монстр не убивает кролика, но обнуляет все накопленные очки, после чего кролик оказывается в конце этого ребра.
После прохождения ребра монстр на нем обновляется, поэтому при многократном прохождении одного и того же ребра эффекты монстра срабатывают каждый раз.
Поскольку кролик не знает структуру лабиринта, он решил двигаться случайным образом: начиная из $S$, он каждый раз независимо выбирает одно из исходящих ребер с равной вероятностью, активирует эффект монстра на этом ребре и переходит в его конец. Когда кролик впервые достигает $T$, блуждание завершается.
Дана структура графа и типы монстров на каждом ребре. Пусть $X$ — случайная величина, равная количеству очков в момент завершения блуждания. Кролик просит вас ответить на два вопроса:
- Чему равно математическое ожидание $X$?
- Чему равна дисперсия $X$?
Поскольку кролик не любит вещественные числа, вам нужно вывести результаты по модулю $998244353$. При заданных условиях можно показать, что ответ всегда является рациональным числом, и если представить его в виде несократимой дроби, знаменатель не будет кратен $998244353$.
Входные данные
Данные считываются из стандартного ввода.
Первая строка содержит четыре целых числа $n, m, S, T$, обозначающие количество вершин, количество ребер, начальную вершину и конечную вершину соответственно.
Далее следуют $m$ строк, каждая из которых содержит три целых числа $x, y, o$, описывающих ориентированное ребро из $x$ в $y$ с монстром типа $o$.
Выходные данные
Вывод осуществляется в стандартный вывод.
Выведите одну строку с двумя целыми числами: первое число — математическое ожидание очков, второе — дисперсия очков.
Примеры
Пример 1
2 2 1 2 1 1 1 1 2 1
Выходные данные 1
2 2
Примечание 1
Из вершины $1$ есть петля и ребро, ведущее в вершину $2$. На каждом ребре $o = 1$, поэтому количество очков равно количеству шагов в случайном блуждании.
Для $x > 0$ итоговое количество очков равно $x$ тогда и только тогда, когда кролик сначала проходит петлю в вершине $1$ ровно $x-1$ раз, а на $x$-й раз переходит в вершину $2$. Таким образом, вероятность того, что количество очков равно $x$, составляет $2^{-x}$. Следовательно, математическое ожидание равно $$\sum_{x=1}^\infty x2^{-x} = 2,$$ а дисперсия равна $$\sum_{x=1}^{+\infty} (x-2)^2 2^{-x} = 2.$$
Подзадачи
Для всех тестовых данных:
- $2 \le n \le 100$, $1 \le m \le n^2$;
- $1 \le S, T \le n$, $S \neq T$;
- $1 \le x, y \le n$, $0 \le o \le 1$;
- Из любой вершины существует путь до $T$.
Подзадача 1 (4 балла): $o = 0$
Подзадача 2 (24 балла): $o = 1$
Подзадача 3 (8 баллов): $m = n-1$, в графе только $S$ имеет входящую степень $0$, и только $T$ имеет исходящую степень $0$
Подзадача 4 (20 баллов): в графе нет циклов
Подзадача 5 (44 балла): без дополнительных ограничений
Оценка
Для каждого теста вы получаете $50\%$ баллов за каждый правильно отвеченный вопрос. Итоговый балл за подзадачу равен минимуму баллов за все тесты в этой подзадаче.
Примечание
Для случайной величины $X$, принимающей значения из множества натуральных чисел, если вероятность $X = x$ равна $P_x$, то математическое ожидание определяется как $$\mathbb{E}[X] = \sum_{x = 0}^{+\infty} x P_x,$$ а дисперсия $X$ определяется как $$\text{Var}[X] = \mathbb{E}[(X - \mathbb{E}[X])^2] = \sum_{x=0}^{+\infty} (x-\mathbb{E}[X])^2 P_x.$$