Preparando MOJI
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$$$.
3 0 1 1 2 3 1 3
3
3 1 1 1 2 3 1 3 2 3
2
Informação
Provedor Codeforces
Código CF1400G
Tags
Submetido 0
BOUA! 0
Taxa de BOUA's 0%
Datas 09/05/2023 10:05:51
Relacionados