CF1792F1 Graph Coloring (easy version)

本题的简单版与困难版的唯一区别在于 $ n $ 的限制。 给定一个有 $ n $ 个顶点的无向完全图。完全图是指任意两个顶点之间都有一条边相连。你需要将图中的每条边涂成红色或蓝色（每条边只能涂一种颜色）。 对于一个顶点集合 $ S $，如果对于 $ S $ 中的任意一对顶点 $ (v_1, v_2) $，都存在一条仅经过 $ S $ 中顶点且只经过红色边的路径从 $ v_1 $ 到 $ v_2 $，则称 $ S $ 是红连通的。同理，如果对于 $ S $ 中的任意一对顶点 $ (v_1, v_2) $，都存在一条仅经过 $ S $ 中顶点且只经过蓝色边的路径从 $ v_1 $ 到 $ v_2 $，则称 $ S $ 是蓝连通的。 你需要对图进行涂色，使得： - 至少存在一条红色边； - 至少存在一条蓝色边； - 对于每一个满足 $ |S| \ge 2 $ 的顶点集合 $ S $，$ S $ 要么是红连通的，要么是蓝连通的，但不能同时两者都是。 请计算有多少种不同的涂色方案，并将答案对 $ 998244353 $ 取模后输出。

第一行也是唯一一行包含一个整数 $ n $（$ 3 \le n \le 5 \cdot 10^3 $）。

输出一个整数，表示不同的涂色方案数，对 $ 998244353 $ 取模。

由 ChatGPT 4.1 翻译