#include <iostream> #include <vector> #include <string> #include <sstream> #include <deque> #include <algorithm> using namespace std; int n; // 頂点数 vector<vector<int>> R; // グラフの隣接リスト(1-indexed) vector<int> visited; // 探索済みフラグ(1-indexed) // DFS 関数:頂点 x から探索し、化学構造を表す文字列(deque<string>)を返す deque<string> dfs(int x) { deque<string> dq; // 現在の頂点 x に対して "methyl" を末尾に追加 dq.push_back("methyl"); visited[x] = 1; // x の隣接頂点を順に探索 for (int nxt : R[x]) { if (!visited[nxt]) { // 未訪問の頂点の場合、まず直前に ")" を先頭に追加 dq.push_front(")"); // 再帰的に隣接頂点を探索 deque<string> sub = dfs(nxt); // 返ってきた deque の末尾に現在の dq の内容を連結する for (const string &s : dq) { sub.push_back(s); } // 連結後の deque を dq に更新 dq = move(sub); // 探索が終わった枝を "(" で囲むため、先頭に "(" を追加 dq.push_front("("); } } return dq; } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); // 入力:頂点数の読み込み cin >> n; cin.ignore(); // 改行を読み捨てる // グラフと探索フラグの初期化(頂点は 1-indexed とする) R.resize(n + 1); visited.assign(n + 1, 0); // 各頂点について、隣接頂点の情報を入力する // 各行には "H" か頂点番号が空白区切りで与えられる for (int i = 1; i <= n; i++){ string line; getline(cin, line); istringstream iss(line); string token; while (iss >> token) { if (token != "H") { int j = stoi(token); // 双方向にエッジを張る R[i].push_back(j); R[j].push_back(i); } } } // 重複する隣接頂点を削除(Python の list(set(...)) と同等) for (int i = 0; i <= n; i++){ sort(R[i].begin(), R[i].end()); R[i].erase(unique(R[i].begin(), R[i].end()), R[i].end()); } // DFS を開始(根は頂点 1) deque<string> ans = dfs(1); // DFS から返ってきた deque の最後の要素を削除 if (!ans.empty()) { ans.pop_back(); } // 末尾に "methane" を追加 ans.push_back("methane"); // deque の内容を連結して出力 string output; for (const string &s : ans) { output += s; } cout << output << "\n"; return 0; }