{"raw_statement":[{"iden":"statement","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"},{"iden":"input","content":"The 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."},{"iden":"output","content":"For 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."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**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$$","simple_statement":"You are given n students, each with a unique name. Initially, each student is in their own team. You need to handle q queries of two types:\n\n- Type 1: Merge the teams of two students.\n- Type 2: Check if two students are in the same team.\n\nFor each type 2 query, print \"yes\" if they are in the same team, \"no\" otherwise.","has_page_source":false}