Hexadecimal likes drawing. She has drawn many graphs already, both directed and not. Recently she has started to work on a still-life «interesting graph and apples». An undirected graph is called interesting, if each of its vertices belongs to one cycle only — a funny ring — and does not belong to any other cycles. A funny ring is a cycle that goes through all the vertices just once. Moreover, loops are funny rings too.

She has already drawn the apples and some of the graph edges. But now it is not clear, how to connect the rest of the vertices to get an interesting graph as a result. The answer should contain the minimal amount of added edges. And furthermore, the answer should be the lexicographically smallest one. The set of edges (x₁, y₁), (x₂, y₂), ..., (x_n, y_n), where x_i ≤ y_i, is lexicographically smaller than the set (u₁, v₁), (u₂, v₂), ..., (u_n, v_n), where u_i ≤ v_i, provided that the sequence of integers x₁, y₁, x₂, y₂, ..., x_n, y_n is lexicographically smaller than the sequence u₁, v₁, u₂, v₂, ..., u_n, v_n. If you do not cope, Hexadecimal will eat you. ...eat you alive.