背景

    有n个人一同出去玩,每个人有一张火车票。由于火车票实行实名制,每张火车票也对应一个人。

描述

    由于某种原因,现在出现了以下情况:每个人手中有一张票,这张票可能是自己的也可能是别人的。现在任意两个人之间可以交换手中的票,求最少进行多少次交换使得每个人都拿到自己的票。假定交换是依次进行的,即同一时刻只进行一次交换,我们也想知道,第一步有多少种方案,能保证交换次数最少。

输入格式

    输入有2行,第一行有两个用空格隔开的正整数n、k(k代表任务种类,详见输出格式),第二行有n个用空格隔开的正整数,第i个为Pi,代表着第i个人手中的票是第Pi个人的。

输出格式

    如果k=1,那么输出只有一个整数,表示最少交换的次数;如果k=2,那么输出有两行,第一行是一个整数,表示最少交换的次数,第二行有一个整数,表示第一步的方案数。

样例输入

3 2
2 3 1

样例输出

2
3

数据范围与约定

样例解释

  • 方案一:第1个人和第2个人交换车票,再和第3个人交换车票。
  • 方案二:第2个人和第3个人交换车票,再和第1个人交换车票。
  • 方案三:第3个人和第1个人交换车票,再和第2个人交换车票。

来源

经典问题