Find root from child adjacency lists

You're given an unordered list describing a rooted n-ary tree. Each item is a record of the form {id: int, children: set<int>} listing a node's direct children; parent links are not provided. All node ids are unique, and every non-root node appears exactly once in some children set. Find and return the root node id. Describe the algorithm, data structures used, time and space complexity, and how you would detect/handle invalid inputs such as multiple roots, cycles, or missing references.