{"problem":{"name":"190. Contact Tracing","description":{"content":"During the coronavirus pandemic, your town is attempting to trace the origins of recent COVID-19 cases. You're given a list of people who had the disease, and who they got it from, and you're trying ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10269190"},"statements":[{"statement_type":"Markdown","content":"During the coronavirus pandemic, your town is attempting to trace the origins of recent COVID-19 cases.\n\nYou're given a list of people who had the disease, and who they got it from, and you're trying to find the names of \"superspreaders\". For this problem, we'll define a _superspreader_ as someone who gave at least three other people COVID-19.\n\nGiven this information, your task is to figure out the names of all of the superspreaders in the town.\n\nThe first line of input contains a single positive integer $n$: the number of people in the town.\n\nThe next $n$ lines contain two space-separated strings: the name of each person, and the name of the person they got the coronavirus from. Exactly one person in the town will have \"OTHER\" (no quotes) as the person they got the disease from, indicating that this person got the disease from a different town.\n\nOutput $k$ lines, where $k$ is the number of superspreaders in the town. On each line, print the name of each superspreader in the order they were given in the input.\n\nIf there aren't any superspreaders in the town, output \"NONE\" (no quotes).\n\n## Input\n\nThe first line of input contains a single positive integer $n$: the number of people in the town.The next $n$ lines contain two space-separated strings: the name of each person, and the name of the person they got the coronavirus from. Exactly one person in the town will have \"OTHER\" (no quotes) as the person they got the disease from, indicating that this person got the disease from a different town.\n\n## Output\n\nOutput $k$ lines, where $k$ is the number of superspreaders in the town. On each line, print the name of each superspreader in the order they were given in the input.If there aren't any superspreaders in the town, output \"NONE\" (no quotes).\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of people.  \nLet $ P = \\{p_1, p_2, \\dots, p_n\\} $ be the set of person names.  \nLet $ S: P \\to P \\cup \\{\\text{OTHER}\\} $ be the transmission function, where $ S(p_i) $ is the name of the person from whom $ p_i $ contracted COVID-19.  \n\n**Constraints**  \n1. Exactly one person $ p_j $ satisfies $ S(p_j) = \\text{OTHER} $.  \n2. For all $ p_i \\in P $, $ S(p_i) \\in P \\cup \\{\\text{OTHER}\\} $.  \n\n**Objective**  \nDefine the out-degree function $ d: P \\to \\mathbb{Z}_{\\geq 0} $, where $ d(x) = |\\{ p_i \\in P \\mid S(p_i) = x \\}| $, i.e., the number of people who contracted the virus from $ x $.  \n\nA person $ x \\in P $ is a *superspreader* if $ d(x) \\geq 3 $.  \n\nOutput the names of all superspreaders in the order they appear in the input. If no superspreaders exist, output \"NONE\".","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10269190","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}