CF1792D.Fixed Prefix Permutations
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
You are given n permutations a1,a2,…,an , each of length m . Recall that a permutation of length m is a sequence of m distinct integers from 1 to m .
Let the beauty of a permutation p1,p2,…,pm be the largest k such that p1=1,p2=2,…,pk=k . If p1=1 , then the beauty is 0 .
The product of two permutations p⋅q is a permutation r such that rj=qpj .
For each i from 1 to n , print the largest beauty of a permutation ai⋅aj over all j from 1 to n (possibly, i=j ).
输入格式
The first line contains a single integer t ( 1≤t≤104 ) — the number of testcases.
The first line of each testcase contains two integers n and m ( 1≤n≤5⋅104 ; 1≤m≤10 ) — the number of permutations and the length of each permutation.
The i -th of the next n lines contains a permutation ai — m distinct integers from 1 to m .
The sum of n doesn't exceed 5⋅104 over all testcases.
输出格式
For each testcase, print n integers. The i -th value should be equal to the largest beauty of a permutation ai⋅aj over all j ( 1≤j≤n ).
输入输出样例
输入#1
3 3 4 2 4 1 3 1 2 4 3 2 1 3 4 2 2 1 2 2 1 8 10 3 4 9 6 10 2 7 8 1 5 3 9 1 8 5 7 4 10 2 6 3 10 1 7 5 9 6 4 2 8 1 2 3 4 8 6 10 7 9 5 1 2 3 4 10 6 8 5 7 9 9 6 1 2 10 4 7 8 3 5 7 9 3 2 5 6 4 8 1 10 9 4 3 7 5 6 1 10 8 2
输出#1
1 4 4 2 2 10 8 1 6 8 10 1 7