problem85.cpp

#include <bits/stdc++.h>
using namespace std;

class MagicalKingdom {
  int n;  // number of castles
  vector<vector<int>> adj;  // adjacency list

public:
  void readInput() {
    cin >> n;
    adj.resize(n);
    cin.ignore(); // clear newline after n

    for (int i = 0; i < n; ++i) {
      string line;
      getline(cin, line);
      istringstream iss(line);
      int v;
      while (iss >> v) {
        adj[i].push_back(v);
      }
    }
  }

  vector<int> bfsExplore() {
    vector<int> order;
    vector<bool> visited(n, false);
    queue<int> q;

    q.push(0);
    visited[0] = true;

    while (!q.empty()) {
      int u = q.front();
      q.pop();
      order.push_back(u);

      for (int v : adj[u]) {
        if (!visited[v]) {
          visited[v] = true;
          q.push(v);
        }
      }
    }
    return order;
  }

  void display() {
    vector<int> result = bfsExplore();
    cout << endl;
    for (int i = 0; i < result.size(); ++i) {
      if (i) cout << " ";
      cout << result[i];
    }
    cout << endl;
  }
};

int main() {
  MagicalKingdom king;
  king.readInput();
  king.display();
  return 0;
}