{"raw_statement":[{"iden":"statement","content":"Our beloved detective, Sherlock is currently trying to catch a serial killer who kills a person each day. Using his powers of deduction, he came to know that the killer has a strategy for selecting his next victim.\n\nThe killer starts with two potential victims on his first day, selects one of these two, kills selected victim and replaces him with a new person. He repeats this procedure each day. This way, each day he has two potential victims to choose from. Sherlock knows the initial two potential victims. Also, he knows the murder that happened on a particular day and the new person who replaced this victim.\n\nYou need to help him get all the pairs of potential victims at each day so that Sherlock can observe some pattern."},{"iden":"input","content":"First line of input contains two names (length of each of them doesn't exceed 10), the two initials potential victims. Next line contains integer _n_ (1 ≤ _n_ ≤ 1000), the number of days.\n\nNext _n_ lines contains two names (length of each of them doesn't exceed 10), first being the person murdered on this day and the second being the one who replaced that person.\n\nThe input format is consistent, that is, a person murdered is guaranteed to be from the two potential victims at that time. Also, all the names are guaranteed to be distinct and consists of lowercase English letters."},{"iden":"output","content":"Output _n_ + 1 lines, the _i_\\-th line should contain the two persons from which the killer selects for the _i_\\-th murder. The (_n_ + 1)\\-th line should contain the two persons from which the next victim is selected. In each line, the two names can be printed in any order."},{"iden":"examples","content":"Input\n\nross rachel\n4\nross joey\nrachel phoebe\nphoebe monica\nmonica chandler\n\nOutput\n\nross rachel\njoey rachel\njoey phoebe\njoey monica\njoey chandler\n\nInput\n\nicm codeforces\n1\ncodeforces technex\n\nOutput\n\nicm codeforces\nicm technex"},{"iden":"note","content":"In first example, the killer starts with _ross_ and _rachel_.\n\n*   After day 1, _ross_ is killed and _joey_ appears.\n*   After day 2, _rachel_ is killed and _phoebe_ appears.\n*   After day 3, _phoebe_ is killed and _monica_ appears.\n*   After day 4, _monica_ is killed and _chandler_ appears."}],"translated_statement":"[{\"iden\":\"statement\",\"content\":\"我们敬爱的侦探夏洛克正在试图抓捕一名连环杀手，该杀手每天杀害一人。通过他的推理能力，他发现杀手在选择下一个受害者时遵循某种策略。\\n\\n杀手在第一天从两名潜在受害者中开始，从中选择一人，杀害被选中的受害者，并用一名新人替换他。此后每天他都重复这一过程。因此，每天他都有两名潜在受害者可供选择。夏洛克知道初始的两名潜在受害者，也知道每天发生的谋杀案以及替换受害者的新人。\\n\\n你需要帮助他获取每天的潜在受害者对，以便夏洛克能够观察出某种规律。\\n\\n输入的第一行包含两个名字（每个名字长度不超过 $10$），即最初的两名潜在受害者。第二行包含一个整数 $n$（$1 ≤ n ≤ 1000$），表示天数。\\n\\n接下来的 $n$ 行，每行包含两个名字（每个名字长度不超过 $10$），第一个是当天被杀害的人，第二个是替换该受害者的新人。\\n\\n输入格式保证一致：被杀害的人必定是当天的两名潜在受害者之一。所有名字均保证互不相同，且仅由小写英文字母组成。\\n\\n请输出 $n + 1$ 行，第 $i$ 行应包含杀手在第 $i$ 次谋杀时所选择的两名潜在受害者。第 $(n + 1)$ 行应包含下一次谋杀所选择的两名潜在受害者。每行中的两个名字可以按任意顺序输出。\\n\\n在第一个例子中，杀手最初选择的是 _ross_ 和 _rachel_。\"},{\"iden\":\"input\",\"content\":\"输入的第一行包含两个名字（每个名字长度不超过 $10$），即最初的两名潜在受害者。第二行包含一个整数 $n$（$1 ≤ n ≤ 1000$），表示天数。接下来的 $n$ 行，每行包含两个名字（每个名字长度不超过 $10$），第一个是当天被杀害的人，第二个是替换该受害者的新人。输入格式保证一致：被杀害的人必定是当天的两名潜在受害者之一。所有名字均保证互不相同，且仅由小写英文字母组成。\"},{\"iden\":\"output\",\"content\":\"请输出 $n + 1$ 行，第 $i$ 行应包含杀手在第 $i$ 次谋杀时所选择的两名潜在受害者。第 $(n + 1)$ 行应包含下一次谋杀所选择的两名潜在受害者。每行中的两个名字可以按任意顺序输出。\"},{\"iden\":\"examples\",\"content\":\"输入\\nross rachel\\n4\\nross joey\\nrachel phoebe\\nphoebe monica\\nmonica chandler\\n输出\\nross rachel\\njoey rachel\\njoey phoebe\\njoey monica\\njoey chandler\\n\\n输入\\nicm codeforces\\n1\\ncodeforces technex\\n输出\\nicm codeforces\\nicm technex\"},{\"iden\":\"note\",\"content\":\"在第一个例子中，杀手最初选择的是 _ross_ 和 _rachel_。 \\n第 $1$ 天后，_ross_ 被杀害，_joey_ 出现。 \\n第 $2$ 天后，_rachel_ 被杀害，_phoebe_ 出现。 \\n第 $3$ 天后，_phoebe_ 被杀害，_monica_ 出现。 \\n第 $4$ 天后，_monica_ 被杀害，_chandler_ 出现。 \"}]\n\n```json\n[{\"iden\":\"statement\",\"content\":\"我们敬爱的侦探夏洛克正在试图抓捕一名连环杀手，该杀手每天杀害一人。通过他的推理能力，他发现杀手在选择下一个受害者时遵循某种策略。\\n\\n杀手在第一天从两名潜在受害者中开始，从中选择一人，杀害被选中的受害者，并用一名新人替换他。此后每天他都重复这一过程。因此，每天他都有两名潜在受害者可供选择。夏洛克知道初始的两名潜在受害者，也知道每天发生的谋杀案以及替换受害者的新人。\\n\\n你需要帮助他获取每天的潜在受害者对，以便夏洛克能够观察出某种规律。\\n\\n输入的第一行包含两个名字（每个名字长度不超过 $10$），即最初的两名潜在受害者。第二行包含一个整数 $n$（$1 ≤ n ≤ 1000$），表示天数。\\n\\n接下来的 $n$ 行，每行包含两个名字（每个名字长度不超过 $10$），第一个是当天被杀害的人，第二个是替换该受害者的新人。\\n\\n输入格式保证一致：被杀害的人必定是当天的两名潜在受害者之一。所有名字均保证互不相同，且仅由小写英文字母组成。\\n\\n请输出 $n + 1$ 行，第 $i$ 行应包含杀手在第 $i$ 次谋杀时所选择的两名潜在受害者。第 $(n + 1)$ 行应包含下一次谋杀所选择的两名潜在受害者。每行中的两个名字可以按任意顺序输出。\\n\\n在第一个例子中，杀手最初选择的是 _ross_ 和 _rachel_。\"},{\"iden\":\"input\",\"content\":\"输入的第一行包含两个名字（每个名字长度不超过 $10$），即最初的两名潜在受害者。第二行包含一个整数 $n$（$1 ≤ n ≤ 1000$），表示天数。接下来的 $n$ 行，每行包含两个名字（每个名字长度不超过 $10$），第一个是当天被杀害的人，第二个是替换该受害者的新人。输入格式保证一致：被杀害的人必定是当天的两名潜在受害者之一。所有名字均保证互不相同，且仅由小写英文字母组成。\"},{\"iden\":\"output\",\"content\":\"请输出 $n + 1$ 行，第 $i$ 行应包含杀手在第 $i$ 次谋杀时所选择的两名潜在受害者。第 $(n + 1)$ 行应包含下一次谋杀所选择的两名潜在受害者。每行中的两个名字可以按任意顺序输出。\"},{\"iden\":\"examples\",\"content\":\"输入\\nross rachel\\n4\\nross joey\\nrachel phoebe\\nphoebe monica\\nmonica chandler\\n输出\\nross rachel\\njoey rachel\\njoey phoebe\\njoey monica\\njoey chandler\\n\\n输入\\nicm codeforces\\n1\\ncodeforces technex\\n输出\\nicm codeforces\\nicm technex\"},{\"iden\":\"note\",\"content\":\"在第一个例子中，杀手最初选择的是 _ross_ 和 _rachel_。 \\n第 $1$ 天后，_ross_ 被杀害，_joey_ 出现。 \\n第 $2$ 天后，_rachel_ 被杀害，_phoebe_ 出现。 \\n第 $3$ 天后，_phoebe_ 被杀害，_monica_ 出现。 \\n第 $4$ 天后，_monica_ 被杀害，_chandler_ 出现。 \"}]\n```","sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ P_0 = \\{v_1, v_2\\} $ be the initial pair of potential victims, where $ v_1, v_2 $ are distinct strings.  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of days.  \nFor each day $ i \\in \\{1, \\dots, n\\} $, let $ (m_i, r_i) $ be the pair where $ m_i $ is the murdered victim and $ r_i $ is the replacement victim.\n\n**Constraints**  \n1. $ 1 \\leq n \\leq 1000 $  \n2. All names are distinct, non-empty strings of lowercase English letters, each of length ≤ 10.  \n3. For each $ i \\in \\{1, \\dots, n\\} $, $ m_i \\in P_{i-1} $, and $ r_i \\notin P_{i-1} $.  \n\n**Objective**  \nCompute the sequence of pairs $ P_0, P_1, \\dots, P_n $, where for each $ i \\in \\{1, \\dots, n\\} $:  \n$$\nP_i = (P_{i-1} \\setminus \\{m_i\\}) \\cup \\{r_i\\}\n$$  \nOutput $ P_0, P_1, \\dots, P_n $, each as an unordered pair of names.","simple_statement":null,"has_page_source":false}