#include <iostream>
#include <memory>
#include <sstream>
#include <string>
#include "Hash.hpp"

constexpr std::size_t hashdim = 32;

struct Item;
using ItemPtr = std::shared_ptr<Item>;
using Dependencies = Hash<std::string, ItemPtr>;
struct Item {
   Item(std::string name) :
      name(std::move(name)), dependencies(hashdim), reversed(hashdim) {
   }
   std::string name;
   Dependencies dependencies; /* this item depends on these other items */
   Dependencies reversed;     /* items that depend on us */
};

int main() {
   Hash<std::string, ItemPtr> items(hashdim);

   /* lookup an item by name and create it, if it does not exist yet */
   auto lookup = [&items](const std::string& name) -> ItemPtr {
      auto it = items.find(name);
      if (it == items.end()) {
	 auto item = std::make_shared<Item>(name);
	 std::tie(it, std::ignore) = items.insert(std::make_pair(name, item));
      }
      return it->second;
   };

   /* build data structure */
   std::string line;
   while (std::getline(std::cin, line)) {
      std::istringstream in(line);
      std::string name;
      if (!(in >> name)) continue;
      auto item = lookup(name);
      std::string depname;
      while (in >> depname) {
	 auto dep = lookup(depname);
	 item->dependencies.insert(std::make_pair(depname, dep));
	 dep->reversed.insert(std::make_pair(name, item));
      }
   }

   /* topological sort */
   while (items.size() > 0) {
      std::size_t removed = 0;
      auto it = items.begin();
      while (it != items.end()) {
	 auto next = it; ++next;
	 auto item = it->second;
	 if (item->dependencies.size() == 0) {
	    /* no dependencies left for item:
	       print it and wipe it entirely
	       from our data structure */
	    std::cout << item->name << std::endl;
	    for (auto& revdepobj: item->reversed) {
	       auto revdep = revdepobj.second;
	       auto it = revdep->dependencies.find(item->name);
	       revdep->dependencies.erase(it);
	    }
	    items.erase(it);
	    ++removed;
	 }
	 it = next;
      }
      if (removed == 0) {
	 std::cerr << "reference cycle!" << std::endl; break;
      }
   }

   for (auto& object: items) {
      auto item = object.second;
      std::cout << item->name << ":";
      for (auto& depobj: item->dependencies) {
	 auto dep = depobj.second;
	 std::cout << " " << dep->name;
      }
      std::cout << std::endl;
   }
}