Given a digraph G = (V, E), print the strongly connected component graph G_SCC = (V_SCC, E_SCC).

Labeling of vertices in V_SCC should be done as follows:

For vertex v in V_SCC , let us define order-id(v) = min{label(v_i) | v_i is part of v in V_SCC}

Vertex v in V_SCC with lowest value of order-id(v) gets label 0, vertex with second lowest value gets label 1 and so on.

Input

The graph is given in the adjacency list format. The first number is n, the number of vertices, which will be an integer ≥ 1. The vertex set is assumed to be V = {0, 1, . . . , n − 1}. Following this number n, there are n lines, where, the i^th line (1^st , 2^nd ...)  corresponds to the adjacency list of node numbered i-1 (0,1,...). Each adjacency list is a sequence of vertex ids (between 0 and n − 1) and ends with -1.

Output

Print the number of strongly connected components.

From the next line , print the sorted adjacency list of each SCC appended with -1

Constraints

2 <= n <= 1000

TIme - 1s

Example 1:

Input:

9 
1 -1 
4 3 2 -1 
5 -1 
-1 
0 -1 
6 -1 
7 -1 
8 -1 
2 -1 

Output:

3
1 2 -1
-1
-1

Explanation:

In the above example, there will be 3 SCCs : {0, 1, 4}, {2, 5, 6, 7, 8} and {3}.

SCCs of {0, 1, 4}, {2, 5, 6, 7, 8}, {3} have order-ids 0, 2 and 3 respectively. Therefore, {0, 1, 4} gets label 0, {2, 5, 6, 7, 8} gets label 1 and {3} gets label 2. There are two edges (0, 1) and (0, 2) in the condensed graph G_SCC. Verify the same in the following diagram:

Example 2:

Input:

10
1 -1
9 -1
4 5 7 9 -1
4 -1
-1
4 -1
1 8 -1
-1
-1
1 -1

Output:

9
1 -1
-1
1 4 5 7 -1
4 -1
-1
4 -1
1 8 -1
-1
-1