题目 B：保持冷静，保持社交距离 (Keep Calm and Social Distancing)

题目描述

一场盛大的技术会议即将在下周举行。你刚收到邀请，准备去和软件开发大咖们交流。你开发了一款新应用，想尽可能多地向参会者推广，但你发现时间只够见 $K$ 个人。

由于 2020 年的特殊情况，所有人必须保持社交距离。为了让你的应用推广最有效，你决定挑选 $K$ 个彼此之间距离最远的参与者。

社交距离的定义：

• 共有 $N$ 名参与者（编号 $1$ 到 $N$）。
• 每个参与者最多只有两个朋友。
• 友谊是双向的（A 是 B 的朋友，则 B 也是 A 的朋友）。
• 两人之间的社交距离 $dist(A, B)$ 是连接 A 和 B 的最短社交关系链的长度。
  • 如果 A 和 B 是朋友，$dist = 1$。
  • 如果 A 和 B 不是朋友但有共同好友，$dist = 2$。
  • 如果 A 和 B 之间不存在任何连接路径，$dist = \infty$（无穷大）。
• 一个集合 $S$ 的社交距离 $dist(S)$ 定义为集合中任意两个不同成员之间 $dist$ 的最小值。

任务： 找到一个包含 $K$ 个人的集合 $S$，使得 $dist(S)$ 最大化。即：让这 $K$ 个人中距离最近的那一对人的距离尽可能大。

输入格式

• 第一行包含三个空格分隔的整数：$N$（参与者人数，$2 \le N \le 10^6$）、$M$（好友关系对数，$0 \le M \le N$）和 $K$（你要见的人数，$2 \le K \le N$）。
• 接下来的 $M$ 行，每行包含两个整数 $a_i, b_i$，表示 $a_i$ 和 $b_i$ 是朋友。保证没有重复的友谊，且不会有人和自己是朋友。

输出格式

输出两行：

1. 第一行：挑选出的 $K$ 个人之间的最小距离的最大值。如果这 $K$ 个人可以完全互不相通，则输出单词 infinity。
2. 第二行：这 $K$ 个人的编号（顺序不限）。