405053: GYM101755 F Tree Restoration
Memory Limit:256 MB
Time Limit:2 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
F. Tree Restorationtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output
There is a tree of n vertices. For each vertex a list of all its successors is known (not only direct ones). It is required to restore the tree or to say there is no such tree.
InputThe first line contains a single integer n (1 ≤ n ≤ 1000) — the number of vertices in the tree.
Each of the next n lines contains an integer ci (0 ≤ ci ≤ n) — the number of successors of vertex i, and then ci distinct integers aij (1 ≤ aij ≤ n) — the indices of successors of vertex i.
OutputIf the answer does not exist, output «NO».
Otherwise, in the first line output «YES», and then output n - 1 lines containing two integers each — indices of parent and child. Pairs (parent, child) can be output in any order.
ExamplesInput5Output
4 2 3 4 5
3 3 4 5
2 4 5
1 5
0
YESInput
1 2
2 3
3 4
4 5
5Output
4 2 3 4 5
3 3 4 5
0
1 5
0
YESInput
1 2
2 3
2 4
4 5
3Output
3 2 3 1
3 3 1 2
3 1 2 3
NO