#P17810. [ONTAK 2023]PAR

[ONTAK 2023]PAR

题目描述

有 nn 个人,其中 mm 对互为朋友。每个人需要选择一个 11 到 2n2n 之间的整数,表示自己的政治偏好。

如果一对朋友所选整数之差的绝对值大于或等于 nn,他们的友谊就会受到威胁。 求有多少种赋值方式,使所有朋友对的友谊都不受威胁。答案对 998244353998244353 取模。

输入格式

第一行两个整数 n,mn,m。接下来 mm 行,每行两个整数 ui,viu_i,v_i,表示一对朋友。没有自环或重复的朋友对。

输出格式

输出合法赋值数量模 998244353998244353 的结果。

数据范围

1≤n≤151\le n\le15,0≤m≤n(n−1)/20\le m\le n(n-1)/2。每个点的取值范围始终是 [1,2n][1,2n],与它所在连通分量的大小无关。

样例

3 1
1 2
144