考虑一个抽象的投票过程。例如,这可能是 2019 年为“Bullet for My Valentine”乐队的最佳歌曲投票。
共有 $n$ 个人参与投票,有 $m$ 个选项可供选择。每个人都形成了自己的偏好列表,其中包含部分选项,按从最偏好到最不偏好的顺序排列。注意,某些选项可能不在偏好列表中——这样的选项不仅是不太偏好,而是不可接受的。
投票按轮次进行。
在第一轮中,每个人都为他们偏好列表中的第一个选项投票。统计每个选项的得票数并向所有人公布。
在随后的每一轮中,每个人都打算为他们在偏好列表中,且在上一轮中获得票数最多的选项投票。如果有多个这样的选项,则选择在偏好列表中出现较早的那一个。
在每一轮开始前,会询问是否有人打算与上一轮投出不同的票。如果不是,则不再进行该轮投票,并将上一轮的结果宣布为最终投票结果。否则,进行投票,并像第一轮一样,再次统计每个选项的得票数并向所有人公布。注意,之前轮次的投票结果将被忽略。
这种投票过程对你来说看起来非常繁琐,最重要的是,它看起来可能永远无法得出结果!为了证明你的观点,请提出 $n$、$m$ 以及偏好列表的值,使得投票至少进行 $100$ 轮。
输入格式
输入仅包含一行,为一个整数 $p$ —— 所需的轮数。
共有两组测试用例。在测试用例 1 中,$p = 2$。在测试用例 2 中,$p = 100$。
输出格式
输出两个整数 $n$ 和 $m$ ($1 \le n \le 10^5; 1 \le m \le 2 \cdot 10^5$) —— 分别为人数和选项数,随后输出 $n$ 个偏好列表。
每个偏好列表必须由 $k_i$ ($1 \le k_i \le m$) 描述 —— 列表中的选项数量,随后是 $k_i$ 个不同的整数 $a_{i,j}$ ($1 \le a_{i,j} \le m$) —— 列表中的选项标识符,按从最偏好到最不偏好的顺序排列。
所有 $k_i$ 的总和不得超过 $2 \cdot 10^5$。
样例
输入 1
2
输出 1
4 5 2 1 2 1 2 3 5 1 3 2 2 3
说明
考虑样例测试用例。
在第一轮中,每个人都为他们列表中的第一个选项投票。因此,第一人投给选项 1,第二人和第四人投给选项 2,第三人投给选项 5。
在第二轮中,看到选项 2 现在处于领先地位,第一人会将他们的投票从选项 1 改为选项 2。其他人将保持他们的投票不变。特别地,第三人将保持他投给选项 5 的票,因为在第一轮中选项 5 和选项 1 都获得了一票,但选项 5 在他们的列表中更靠前。
最后,由于没有人愿意再改变他们的投票,第三轮不再进行。已经进行了两轮投票,满足 $p = 2$。