A13726 | Mercenaries

Polycarp plays a (yet another!) strategic computer game. In this game, he leads an army of mercenaries.

Polycarp wants to gather his army for a quest. There are $n$ mercenaries for hire, and the army should consist of some subset of them.

The $i$ -th mercenary can be chosen if the resulting number of chosen mercenaries is not less than $l_i$ (otherwise he deems the quest to be doomed) and not greater than $r_i$ (he doesn't want to share the trophies with too many other mercenaries). Furthermore, $m$ pairs of mercenaries hate each other and cannot be chosen for the same quest.

How many non-empty subsets does Polycarp need to consider? In other words, calculate the number of non-empty subsets of mercenaries such that the size of this subset belongs to $[l_i, r_i]$ for each chosen mercenary, and there are no two mercenaries in the subset that hate each other.

The answer may be large, so calculate it modulo $998244353$ .

The first line contains two integers $n$ and $m$ ( $1 \le n \le 3 \cdot 10^5$ , $0 \le m \le \min(20, \dfrac{n(n-1)}{2})$ ) — the number of mercenaries and the number of pairs of mercenaries that hate each other.

Then $n$ lines follow, the $i$ -th of them contains two integers $l_i$ and $r_i$ ( $1 \le l_i \le r_i \le n$ ).

Then $m$ lines follow, the $i$ -th of them contains two integers $a_i$ and $b_i$ ( $1 \le a_i < b_i \le n$ ) denoting that the mercenaries $a_i$ and $b_i$ hate each other. There are no two equal pairs in this list.

Print one integer — the number of non-empty subsets meeting the constraints, taken modulo $998244353$ .