permutation

题目描述

你最近学习了逆序数的 $O(n\log n)$ 算法。

给定一个长度为 $n$ 的排列 $P$，定义一次操作如下：

选择两个下标 $i,j$，满足

然后交换 $P_i$ 和 $P_j$。

对于排列 $A$ 和排列 $B$，如果排列 $A$ 经过若干次上述操作可以变成排列 $B$，则称 $B$ 是从 $A$ 可达的。这里“若干次”可以为 $0$ 次，因此每个排列都可以到达自身。

现在给定 $m$ 个长度为 $n$ 的排列 $P_1,P_2,\ldots,P_m$。记 $f_i$ 为满足“$P_i$ 可以从 $P_j$ 可达”的下标 $j$ 的个数。请计算所有 $f_i$。

注意：输入中的排列可以重复出现，计数时每个出现位置都要单独计算。

输入格式

第一行包含两个正整数 $n,m$，分别表示排列长度和排列个数。

接下来 $m$ 行，每行 $n$ 个整数，描述一个 $1\sim n$ 的排列。

输出格式

输出 $m$ 行，其中第 $i$ 行输出一个整数 $f_i$。

样例一

输入

3 3
1 2 3
3 1 2
2 3 1

输出

3
1
1

样例二

输入

2 2
1 2
1 2

输出

2
2

数据范围与提示

• 子任务 $1$（$10$ 分）：$n\le 7,\ m\le 2000$。
• 子任务 $2$（$22$ 分）：$n\le 8$。
• 子任务 $3$（$19$ 分）：$m\le 2000$。
• 子任务 $4$（$49$ 分）：无特殊限制。

对于 $100\%$ 的数据：