Быстрая топологическая сортировка, когда важен порядок узлов?

Я решаю эту задачу на Hackerrank. Резюме проблемы:

Вы пытаетесь восстановить последовательность M различных целых чисел в диапазоне [1, 10^6]. Вам дано 1 ‹= N ‹= 10^3 подпоследовательности длины 2 ‹= K ‹= 10^3. Если возможны две последовательности, вернуть ту, которая лексикографически меньше.

Мой алгоритм следующий:

1. Создайте вершину для каждого отдельного целого числа. Храните их в хэш-карте.

2. Для каждой строки, если i стоит перед j в строке, добавьте ребро от i до j. Отслеживайте степень вхождения каждой вершины.

3. Составьте приоритетную очередь, ключом которой является значение каждой вершины. Ставим в очередь все вершины со степенью вхождения 0.

4. Пока очередь не пуста: вытолкнуть верхнюю вершину. Уменьшите степень вхождения каждого из его дочерних элементов.

Мои ответы верны, но у меня превышено ограничение по времени для больших тестовых наборов. Я думаю, что приоритетная очередь является узким местом, но я не могу придумать, как сохранить вершины, отсортированные по значению, менее O(log n). Мой код выглядит следующим образом, за исключением класса Vertex, чтобы сделать его короче --- в основном это просто геттеры и сеттеры:

class FavoriteSequence {
    private Map<Integer, Vertex> seen;

    public void solve(int testNumber, Scanner in, PrintWriter out) {
        int numRows = in.nextInt();
        seen = new HashMap<>();

        for (int i = 0; i < numRows; i++) {
            int numInRow = in.nextInt();
            List<Vertex> row = IntStream.range(0, numInRow).mapToObj(x -> getVert(in.nextInt())).collect(
                    Collectors.toList());

            int idx = 0;
            for (Vertex v : row) {
                v.incInDegree(idx);
                v.addChildren(row.subList(++idx, numInRow));
            }
        }

        List<String> ans = new LinkedList<>();
        Queue<Vertex> bfsQ = new PriorityQueue<>(new Comparator<Vertex>() {
            public int compare(Vertex o1, Vertex o2) {
                int valCmp = Integer.compare(o1.getValue(), o2.getValue());
                return valCmp;
            }
        });

        bfsQ.addAll(seen.values().stream().filter(c -> c.getInDegree() == 0).collect(Collectors.toList()));

        while (!bfsQ.isEmpty()) {
            Vertex me = bfsQ.poll();
            ans.add(Integer.toString(me.getValue()));

            for (List<Vertex> cs : me.getChildrens()) {
                for (Vertex c : cs) {
                    if (c.decInDegree() == 0) {
                        bfsQ.add(c);
                    }
                }
            }
        }

        out.println(String.join(" ", ans));
    }

    private Vertex getVert(int idx) {
        Vertex me = seen.get(idx);

        if (me == null) {
            me = new Vertex(idx);
            seen.put(idx, me);
        }

        return me;
    }
}

Что я делаю слишком медленно? Я предоставил свой код, чтобы сделать его конкретным, но я действительно ищу алгоритмический ответ.