AT_pakencamp_2025_day1_j Small Product

頂点 $ 1,2,\ldots,N $ からなる $ M $ 辺の連結な単純無向グラフ $ G $ が与えられます。 $ G $ の $ i $ 番目の辺は、頂点 $ A_i,B_i $ を結んでいます。 $ G $ の頂点 $ x $ のうち、以下の条件を満たすものを全て求めてください。 - $ G $ の $ x $ でない頂点 $ y $ に対する、 $ x $ から $ y $ までの距離の総積は $ K $ 以下である。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ K $ $ A_1 $ $ B_1 $ $ A_2 $ $ B_2 $ $ \vdots $ $ A_M $ $ B_M $

$ 2 $ 行出力せよ。 $ 1 $ 行目には、条件を満たす頂点の個数 $ k $ を出力せよ。 $ 2 $ 行目には、条件を満たす頂点の番号を昇順に $ X_1,X_2,\ldots,X_k $ として以下のように出力せよ。 > $ k $ $ X_1 $ $ X_2 $ $ \ldots $ $ X_k $

### Sample Explanation 1 例えば、 $ x=1 $ としたときを考えます。頂点 $ 1 $ から $ 2,3,4 $ までの距離はそれぞれ $ 1,1,2 $ であるため、総積は $ 2 $ であり、これは $ 3 $ 以下なので条件を満たします。 条件を満たすのは $ x=1,2,3 $ の $ 3 $ つです。 ### Sample Explanation 2 このグラフは完全グラフなので、全ての頂点について距離の総積は $ 1 $ であり、これは $ K = 1 $ 以下なので全ての頂点が条件を満たします。 ### Constraints - $ 2 \leq N \leq 10^5 $ - $ 1 \leq M \leq 10^5 $ - $ 1 \leq K \leq 10^{13} $ - $ 1 \leq A_i < B_i \leq N $ - $ G $ は単純かつ連結 - 入力は全て整数