Convert an undirected simple graph from adjacency lists to an edge list.

Input

The first line contains n. The next n lines list the neighbors of vertices 1 through n; a line may be empty.

• 1 <= n <= 1000

Output

Print every undirected edge u v once, ordered increasingly by u and then v, with u < v.

Example

Input

4
2 3
1 4
1
2

Output

1 2
1 3
2 4