Sequence guessing

John has found a secret door in a pyramid and he needs a secret number sequence to open it. Let us call this sequence as and, only contains distinct natural numbers. People who designed the door wrote identical copies of exact sequence in number of papers to preserve it. Unforatunately, with the time, some numbers are erased in each copy. (it is possible that in some copies numbers are not erased). John managed to collect all the papers. In each of them, all the numbers are distinct. Your task is to help John to find the shortest possible sequence that might have been the original . If there are several possible such sequences, return the lexicographically smallest one. It is guaranteed that such a sequence exists.

Note Sequence is lexicographically less than sequence if and only if there exists such that for all and .

Input Format

In the first line, there is one number denoting the number of copies of . After that there are number of lines. In each pair of lines, first line contains integer denoting the length of the copy. Second line contains space seperated number of integers denoting the copy.

Constraints

All values in one sequence are distinct numbers in range

Output Format

In one line, write the space-separated sequence - the shortest sequence that might have been the original . If there are many such sequences, return the lexicographically smallest one.

Sample Input 0

Sample Output 0

1 2 3 4

Explanation 0

You have 2 copies of the sequence with some missing numbers: and . There are two candidates for the original sequence and , where the first one is lexicographically least.

Solution

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
using namespace std;

int main() {
    int N;
    cin >> N;

    map<int, set<int>> adj;       // adjacency list
    map<int, int> in_degree;      // track in-degrees
    set<int> all_numbers;         // all unique numbers

    for (int i = 0; i < N; ++i) {
        int K;
        cin >> K;
        vector<int> seq(K);
        for (int j = 0; j < K; ++j) {
            cin >> seq[j];
            all_numbers.insert(seq[j]);
            if (j > 0) {
                if (adj[seq[j - 1]].insert(seq[j]).second) {
                    in_degree[seq[j]]++;
                }
            }
            if (!in_degree.count(seq[j])) {
                in_degree[seq[j]] = 0;
            }
        }
    }

    priority_queue<int, vector<int>, greater<int>> pq;
    for (int num : all_numbers) {
        if (in_degree[num] == 0) {
            pq.push(num);
        }
    }

    vector<int> result;
    while (!pq.empty()) {
        int curr = pq.top();
        pq.pop();
        result.push_back(curr);
        for (int next : adj[curr]) {
            in_degree[next]--;
            if (in_degree[next] == 0) {
                pq.push(next);
            }
        }
    }

    for (int i = 0; i < result.size(); ++i) {
        cout << result[i] << (i + 1 == result.size() ? "\n" : " ");
    }

    return 0;
}