{"problem":{"name":"F. Function","description":{"content":"You are given a permutation $a$ obtained from $0$ to $(n -1)$, and a permutation $b$ obtained from $0$ to $(m -1)$. Let's define a function $f$, which maps each integer between $0$ and $(n -1)$, to a","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":131072},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10225F"},"statements":[{"statement_type":"Markdown","content":"You are given a permutation $a$ obtained from $0$ to $(n -1)$, and a permutation $b$ obtained from $0$ to $(m -1)$.\n\nLet's define a function $f$, which maps each integer between $0$ and $(n -1)$, to an integer between $0$ and $(m -1)$.\n\nPlease calculate the number of different functions $f$ satisfying that $f (i) = b_{f (a_i})$ for each $i$.\n\nTwo functions are considered different if and only if there exists at least one integer mapped to different integers in these functions.\n\nThe answer can be a bit large, so you should output it modulo $(10^9 + 7)$ instead.\n\nThe input contains multiple test cases.\n\nFor each test case, the first line contains two integers $n$, $m$ ($1 <= n, m <= 10^5$).\n\nThe second line contains $n$ integers, the $i$-th number of which is $a_{i -1}$ ($0 <= a_{i -1} <= n -1$).\n\nThe third line contains $m$ integers, the $i$-th number of which is $b_{i -1}$ ($0 <= b_{i -1} <= m -1$).\n\nIt is guaranteed that the sum of $n$ and the sum of $m$ in all test cases are no more than $10^6$ respectively.\n\nFor each test case, output \"_Case #x: y_\" in one line (without quotes), where $x$ indicates the case number starting from $1$, and $y$ denotes the answer to the corresponding case.\n\n## Input\n\nThe input contains multiple test cases.For each test case, the first line contains two integers $n$, $m$ ($1 <= n, m <= 10^5$).The second line contains $n$ integers, the $i$-th number of which is $a_{i -1}$ ($0 <= a_{i -1} <= n -1$).The third line contains $m$ integers, the $i$-th number of which is $b_{i -1}$ ($0 <= b_{i -1} <= m -1$).It is guaranteed that the sum of $n$ and the sum of $m$ in all test cases are no more than $10^6$ respectively.\n\n## Output\n\nFor each test case, output \"_Case #x: y_\" in one line (without quotes), where $x$ indicates the case number starting from $1$, and $y$ denotes the answer to the corresponding case.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of students.  \nLet $ S = \\{s_1, s_2, \\dots, s_n\\} $ be the set of distinct student names.  \nLet $ \\mathcal{P} $ be a partition of $ S $, initially $ \\mathcal{P} = \\{ \\{s\\} \\mid s \\in S \\} $.  \nLet $ q \\in \\mathbb{Z}^+ $ be the number of queries.\n\n**Constraints**  \n1. $ 2 \\leq n \\leq 10^5 $  \n2. $ 1 \\leq q \\leq 10^5 $  \n3. Each student name $ s_i $ is a string of length $ 2 \\leq |s_i| \\leq 10 $, with first letter uppercase, rest lowercase, all distinct.  \n4. For each query $ i $:  \n   - $ t_i \\in \\{1, 2\\} $  \n   - $ s_x, s_y \\in S $, $ s_x \\neq s_y $  \n   - If $ t_i = 1 $, merge the sets containing $ s_x $ and $ s_y $ in $ \\mathcal{P} $ (if not already in same set).  \n   - If $ t_i = 2 $, query whether $ s_x $ and $ s_y $ belong to the same set in $ \\mathcal{P} $.  \n5. At least one query of type $ 2 $ exists.\n\n**Objective**  \nFor each query of type $ 2 $, output:  \n$$\n\\begin{cases}\n\\text{\"yes\"} & \\text{if } \\exists\\, P \\in \\mathcal{P} \\text{ such that } s_x \\in P \\text{ and } s_y \\in P \\\\\n\\text{\"no\"} & \\text{otherwise}\n\\end{cases}\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10225F","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}