You are given an undirected, connected, simple graph on n nodes labeled 1 through n. The graph has exactly n edges, which means it is a spanning tree plus exactly one additional edge — so it contains exactly one cycle (there are no self-loops and no repeated edges). The edges are listed in a fixed order. Imagine inserting them one at a time into an initially empty graph: exactly one edge, when inserted, connects two nodes that are already connected by previously inserted edges — that edge is the one that closes the cycle. Output that edge.

Input format

• Line 1: two integers n and m. It is guaranteed that m = n and the graph satisfies the properties above.
• The next m lines: each contains two integers u and v (1-indexed) describing an undirected edge.

Output format

A single line with two integers u v: the endpoints of the redundant edge, printed exactly in the order they appear on that edge's input line (do not reorder them).

Constraints

• 3 ≤ n ≤ 100000
• m = n
• 1 ≤ u, v ≤ n, u ≠ v
• The graph is connected, simple, and contains exactly one cycle. Under these guarantees the redundant edge is unique.

4 4
1 2
2 3
3 4
1 3

1 3

5 5
2 1
3 2
2 4
5 4
5 3

5 3