CF1400G 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 $ .