Challenge: Build Order

Lab Java Intermediate 20 points

A game has n buildings (1 … n) and rules “a must be built before b”. Print an order to build everything. When several buildings are ready, always build the smallest number first. If the rules contain a loop, print impossible.

Input

Line 1: n m. Then m lines a b.

Output

The build order separated by spaces, or impossible.

Example

Input

Output

1 2 3 4 5 6

Sample input available Sample output available

Editor

Java

Hints

Count in-degrees. Buildings with in-degree 0 are ready.

Use a PriorityQueue for the ready buildings so the smallest comes out first. If fewer than n get built, there's a loop.

Solution explanation

Kahn's algorithm with a min-heap: O((n + m) log n), and the answer is always the same single order.

Show solution

import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt();
        ArrayList<ArrayList<Integer>> g = new ArrayList<ArrayList<Integer>>();
        for (int i = 0; i <= n; i++) g.add(new ArrayList<Integer>());
        int[] inDegree = new int[n + 1];
        for (int i = 0; i < m; i++) {
            int a = sc.nextInt(), b = sc.nextInt();
            g.get(a).add(b);
            inDegree[b]++;
        }
        PriorityQueue<Integer> ready = new PriorityQueue<Integer>();   // smallest ready first
        for (int i = 1; i <= n; i++) if (inDegree[i] == 0) ready.offer(i);
        StringBuilder sb = new StringBuilder();
        int built = 0;
        while (!ready.isEmpty()) {
            int b = ready.poll();
            if (built++ > 0) sb.append(' ');
            sb.append(b);
            for (int next : g.get(b)) {
                if (--inDegree[next] == 0) ready.offer(next);
            }
        }
        System.out.println(built < n ? "impossible" : sb.toString());
    }
}

Output

Answer