Challenge: The Useless Cable

Lab Java Intermediate 20 points

Cables are plugged in one by one. Find the first cable that connects two computers that were already connected (it makes a loop). Print it as a b, or none.

Input

Line 1: n m. Then m lines a b, in plug-in order.

Output

The first useless cable, or none.

Example

Input

Output

3 1

Sample input available Sample output available

Editor

Java

Hints

Before plugging a cable in, check whether a and b already share a leader.

Keep reading every cable even after you've found the answer.

Solution explanation

One union-find check per cable: nearly O(m). This is also the key step of Kruskal's algorithm for cheapest networks.

Show solution

import java.util.Scanner;

public class Main {
    static int[] parent;

    static int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt();
        parent = new int[n + 1];
        for (int i = 1; i <= n; i++) parent[i] = i;
        String answer = "none";
        for (int i = 0; i < m; i++) {
            int a = sc.nextInt(), b = sc.nextInt();
            int ra = find(a), rb = find(b);
            if (ra == rb) {
                if (answer.equals("none")) answer = a + " " + b;
            } else {
                parent[ra] = rb;
            }
        }
        System.out.println(answer);
    }
}

Output

Answer