G - Bipartite Partition
Editorial
/
Time Limit: 8 sec / Memory Limit: 1024 MB
配点 : 1600 点
問題文
整数 N が与えられます. 1 から N までの番号のついた N 頂点からなる無向グラフ G を考えます. 以下の条件をすべて満たすグラフ G の個数を 998244353 で割った余りを求めてください.
- G は多重辺や自己ループを含まない.
- G は連結である.
- G の頂点集合の分割 \{S_1,S_2,\cdots\} であって,以下の条件をみたすものが存在する.
- 各 S_i について,|S_i| \geq 2 である.
- 各 S_i について,S_i による誘導部分グラフは,連結な二部グラフである.
誘導部分グラフとは
S をグラフ G の頂点の部分集合とします. このとき,G の S による誘導部分グラフとは,頂点集合が S で,辺集合が「G の辺であって両端が S に含まれるものすべて」であるようなグラフです.
制約
- 2 \leq N \leq 2 \times 10^5
- 入力される値はすべて整数である
入力
入力は以下の形式で標準入力から与えられる.
N
出力
答えを出力せよ.
入力例 1
2
出力例 1
1
入力例 2
3
出力例 2
3
入力例 3
4
出力例 3
38
入力例 4
5
出力例 4
712
入力例 5
12345
出力例 5
503682022