← 返回题目列表

AtCoder · pakencamp_2025_day1_j

J. 小产品

中文机器翻译题面 查看原题

配点 : 400 点

問題文

頂点 1,2,\ldots,N 组成 M 具有连接边的简单无向图 第 G 。 G 的 i 条边是顶点 A_i,B_i 。由

G 的顶点 查找所有满足以下条件的 x 。 不是

  • G 的 x 的顶点 对于 y , 到 x 从 y 的距离的总乘积为 K 下面。

制約

  • 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 简单且串联 输出
  • 所有输入均为整数 如果

入力

输入是按以下格式从标准输入给出的。

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

入力例 1

4 4 3
1 2
1 3
2 3
2 4

出力例 1

3
1 2 3 

例如, x=1 的情况。顶点 到 1 从 2,3,4 的距离是 1,1,2 ,所以总乘积是 2 ,即 3 由于如下,因此满足条件。

满足条件。 x=1,2,3 的 3 一。


入力例 2

4 6 1
1 2
1 3
1 4
2 3
2 4
3 4

出力例 2

4
1 2 3 4 

由于该图是完全图,因此所有顶点的距离的总乘积为 1 ,即 K = 1 因为它在下面,所以所有顶点都满足条件。


入力例 3

6 7 5
1 4
3 5
4 6
1 2
3 4
1 3
4 5

出力例 3

3
1 3 4