Challenge: The Road That Makes a Loop

Lab Python Intermediate 20 points

Roads are built one at a time between n towns. Print the first road (as a b) that connects two towns that were already connected (so it creates a loop), or no loop.

Input

Line 1: n m. Then m lines a b in the order they're built.

Output

a b or no loop.

Example

Input

Output

2 0

Sample input available Sample output available

Editor

Python

Hints

Before joining a and b, check if find(a) == find(b).

If they already share a leader, this road closes a loop.

Solution explanation

Union-find answers “are they already connected?” almost instantly as the roads are added.

Show solution

n, m = map(int, input().split())
parent = list(range(n))


def find(x):
    while parent[x] != x:
        parent[x] = parent[parent[x]]
        x = parent[x]
    return x


answer = "no loop"
for _ in range(m):
    a, b = map(int, input().split())
    ra, rb = find(a), find(b)
    if ra == rb:
        if answer == "no loop":
            answer = f"{a} {b}"
    else:
        parent[rb] = ra
print(answer)

Output

Answer