G. Наемники
ограничение по времени на тест
7 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Поликарп играет в (очередную) стратегическую компьютерную игру. В этой игре он управляет армией наемников.

Поликарп хочет собрать свою армию для выполнения задания. Для найма доступны $$$n$$$ наемников, и армия Поликарпа должна состоять из некоторого подмножества множества доступных наемников.

$$$i$$$-го наемника можно выбрать только в том случае, если итоговое количество выбранных наемников не менее $$$l_i$$$ (иначе этот наемник считает задание слишком опасным) и не более $$$r_i$$$ (он не хочет делить добычу со слишком большим количеством других наемников). Кроме того, $$$m$$$ пар наемников ненавидят друг друга, и из каждой такой пары можно взять на задание не более одного наемника.

Сколько непустых подмножеств наемников Поликарп должен рассмотреть? Другими словами, посчитайте количество подмножеств наемников, которые не содержат пар наемников, ненавидящих друг друга, и размер которых принадлежит отрезку $$$[l_i, r_i]$$$ для каждого наемника из подмножества.

Ответ может быть очень большим, поэтому посчитайте его по модулю $$$998244353$$$.

Входные данные

В первой строке заданы два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n \le 3 \cdot 10^5$$$, $$$0 \le m \le \min(20, \dfrac{n(n-1)}{2})$$$) — количество наемников и количество пар наемников, ненавидящих друг друга, соответственно.

Далее следуют $$$n$$$ строк, в $$$i$$$-й из которых заданы два целых числа $$$l_i$$$ и $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$).

Далее следуют $$$m$$$ строк, в $$$i$$$-й из которых заданы два целых числа $$$a_i$$$ и $$$b_i$$$ ($$$1 \le a_i < b_i \le n$$$), обозначающих, что наемники $$$a_i$$$ и $$$b_i$$$ ненавидят друг друга. Все заданные пары различны.

Выходные данные

Выведите одно целое число — количество подмножеств, удовлетворяющих условию задачи, взятое по модулю $$$998244353$$$.

Примеры
Входные данные
3 0
1 1
2 3
1 3
Выходные данные
3
Входные данные
3 1
1 1
2 3
1 3
2 3
Выходные данные
2