Key Road Problem

B Country has n cities, which are connected by railways such that any two cities are reachable from each other (i.e. the graph is connected). General uim from A Country plans a strategic attack to disrupt the transportation system. He observes that if some railways are destroyed, certain pairs of cities become unreachable from one another. Such a railway is called a key road.

An edge e = (u,v) is a key road if after its removal the graph becomes disconnected. In other words, if we run a DFS and maintain discovery time tin and low-link values low, then an edge \( (u,v) \) is a bridge (key road) if:

[ low[v] > tin[u] ]

General uim only has one shell. He wants to bomb exactly one railway such that after its destruction, there exist at least two cities that cannot reach each other. If there is at least one key road, output any one of them; otherwise, output -1.

Input Format: The input consists of integers describing the graph. The first line contains two integers n and m, which represent the number of cities and railways respectively. Each of the following m lines contains two integers u and v (1-based indices), denoting a bidirectional railway connecting cities u and v.

Output Format: If a key road exists, output two integers (the endpoints of one key road). Otherwise, output -1.

inputFormat

The first line contains two space-separated integers n and m (n is the number of cities and m is the number of railways). The next m lines each contain two integers u and v, representing a railway connecting cities u and v.

outputFormat

Output one line. If a key road exists, output two integers which are the endpoints of the key road (you may output any valid key road). If no key road exists, output -1.

sample

3 2
1 2
2 3

1 2