https://ac.nowcoder.com/acm/contest/12548/L
Graph Coloring University, is interested in permutation. Now she is given a permutation of length nnn, and she finds that if she connects each inverse pair, she will get a graph. Formally, for the given permutation, if i<j and ai>aj, then there will be an undirected edge between node i and node j in the graph.
Then she wants to color this graph. Please achieve poor Simone's dream. To simplify the problem, you just need to find a way of coloring the vertices of the graph such that no two adjacent vertices are of the same color and minimize the number of colors used.
输入描述:
There are multiple test cases. The first line of the input contains an integer T(1≤T≤106), indicating the number of test cases.
For each test case, the first line contains an integer n(1≤n≤106), indicating the length of the permutation.
The second line contains nnn integers a1,a2,...,an, indicating the permutation.
It is guaranteed that the sum of nnn over all test cases does not exceed 106.
输出描述:
For each test case, the first line contains an integer ccc, the chromatic number(the minimal number of colors been used when coloring) of the graph.
The second line contains nnn integers c1,c2,...,cnc_1,c_2,...,c_nc1,c2,...,cn, the color of each node.
Notice that cic_ici should satisfy the limit that 1≤ci≤c.
If there are several answers, it is acceptable to print any of them.