class Codec {
public:

  // Encodes a tree to a single string.
  string serialize(Node* root) {
    string s;
    if (!root) return "#";
    s = to_string(root->val) + " " + to_string(root->children.size());
    for (int i = 0; i < root->children.size(); i++)
      s = s + " " + serialize(root->children[i]);
    return s;
  }

  // Decodes your encoded data to tree.
  Node* deserialize(string data) {
    cur = 0;
    return dfs(data);
  }

  int try_get_val(string& str, int& pos) {
    int val = 0;
    while(pos < str.size()) {
      char c = str[pos];
      if(c >= '0' && c <= '9') {
        val = val * 10 + (c - '0');
        pos++;
      } else break;
    }
    pos++; // skip next ' '
    return val;
  }

  Node* dfs(string& str) {
    if (str[cur] == '#') return NULL;
    int val = try_get_val(str, cur);
    int size = try_get_val(str, cur);
    Node *node = new Node(val);
    for (int i = 0; i < size; ++i)
      node->children.push_back(dfs(str));
    return node;
  }

  int cur;
};