{"raw_statement":[{"iden":"statement","content":"Due to the disorganized structure of his mootels (much like motels but with\nbovine rather than human guests), Farmer John has decided to take up the role of\nthe mootel custodian to restore order to the stalls.\n\nEach mootel has $N$ stalls labeled $1$ through $N$ and $M$ corridors that connect pairs of stalls to each other\nbidirectionally. The $i$ th stall is painted with color $C_i$ and initially has a\nsingle key of color $S_i$ in it. FJ will have to rearrange the keys to appease\nthe cows and restore order to the stalls.\n\nFJ starts out in stall $1$ without holding any keys and is allowed to repeatedly\ndo one of the following moves:\n- Pick up a key in the stall he is currently in. FJ can hold multiple keys at\na time.\n- Place down a key he is holding into the stall he is currently\nin. A stall may hold multiple keys at a time.\n- Enter stall $1$ by\nmoving through a corridor.\n- Enter a stall other than stall $1$ by\nmoving through a corridor. He can only do this if he currently holds a key that\nis the same color as the stall he is entering.\n\nUnfortunately, it seems that the keys are not in their intended locations. To\nrestore order to FJ's mootel, the $i$th stall requires that a single key of\ncolor $F_i$ is in it. It is guaranteed that $S$ is a permutation of $F$.\n\nFor $T$ different mootels, FJ starts in stall $1$ and needs\nto place every key in its appropriate location, ending back in stall $1$. For\neach of the $T$ mootels, please answer if it is possible to do this."},{"iden":"input","content":"The first line contains $T$, the number of mootels (test cases).\n\nEach test case will be preceded by a blank line. Then, the first line \nof each test case contains two integers $N$ and $M$.\n\nThe second line of each test case contains $N$ integers. The $i$-th integer on\nthis line $C_i$ means that stall $i$ has color $C_i$.\n\nThe third line of each test case contains $N$ integers. The $i$-th integer on\nthis line $S_i$ means that stall $i$ initially holds a key of color $S_i$.\n\nThe fourth line of each test case contains $N$ integers. The $i$-th integer on\nthis line $F_i$ means that stall $i$ needs to have a key of color $F_i$ in it.\n\nThe next $M$ lines of each test case follow. The $i$-th of these lines contains\ntwo distinct integers $u_i$ and $v_i$. This represents\nthat a corridor exists between stalls $u_i$ and $v_i$. No corridors are\nrepeated.\n"},{"iden":"output","content":"For each mootel, output `YES` on a new line if there exists a way for FJ to return\na key of color $F_i$ to each stall $i$ and end back in stall $1$. Otherwise,\noutput `NO` on a new line."},{"iden":"note","content":"For the first test case of the first sample, here is a possible sequence of moves:\n\n```\nCurrent stall: 1. Keys held: []. Keys in stalls: [3, 4, 3, 4, 2]\n(pick up key of color 3)\nCurrent stall: 1. Keys held: [3]. Keys in stalls: [x, 4, 3, 4, 2]\n(move from stall 1 to 2, allowed since we have a key of color C_2=3)\nCurrent stall: 2. Keys held: [3]. Keys in stalls: [x, 4, 3, 4, 2]\n(pick up key of color 4)\nCurrent stall: 2. Keys held: [3, 4]. Keys in stalls: [x, x, 3, 4, 2]\n(move from stall 2 to 1 to 4 to 5, allowed since we have keys of colors C_4=4 and C_5=3)\nCurrent stall: 5. Keys held: [3, 4]. Keys in stalls: [x, x, 3, 4, 2]\n(pick up key of color 2 and place key of color 3)\nCurrent stall: 5. Keys held: [2, 4]. Keys in stalls: [x, x, 3, 4, 3]\n(move from stall 5 to 4 to 1 to 3, allowed since we have keys of colors C_4=4 and C_3=2)\nCurrent stall: 3. Keys held: [2, 4]. Keys in stalls: [x, x, 3, 4, 3]\n(pick up key of color 3 and place key of color 4)\nCurrent stall: 3. Keys held: [2, 3]. Keys in stalls: [x, x, 4, 4, 3]\n(move from stall 3 to stall 2 and place key of color 3)\nCurrent stall: 2. Keys held: [2]. Keys in stalls: [x, 3, 4, 4, 3]\n(move from stall 2 to stall 1 and place key of color 2)\nCurrent stall: 1. Keys held: []. Keys in stalls: [2, 3, 4, 4, 3]\n```\n\nFor the second test case of the first sample, there exists no way for FJ to return a key of color\n$F_i$ to each stall $i$ and end back at stall $1$.\n\n$0 \\le M \\le 10^5$, $1 \\le C_i, S_i, F_i, u_i, v_i \\le N \\le 10^5$.   \n$1 \\le T \\le 100$, $1 \\le \\sum N \\le 10^5$, $1 \\le \\sum M \\le 2\\cdot 10^5$.\n\n- Test cases 3-6 satisfy $N,M\\le 8$.\n- Test cases 7-10 satisfy $C_i=F_i$.\n- Test cases 11-18 satisfy no additional constraints.\n"}],"translated_statement":null,"sample_group":[["2\n\n5 5\n4 3 2 4 3\n3 4 3 4 2\n2 3 4 4 3\n1 2\n2 3\n3 1\n4 1\n4 5\n\n4 3\n3 2 4 1\n2 3 4 4\n4 2 3 4\n4 2\n4 1\n4 3\n","YES\nNO\n"],["5\n\n2 0\n1 2\n2 2\n2 2\n\n2 1\n1 1\n2 1\n2 1\n1 2\n\n2 1\n1 1\n2 1\n1 2\n1 2\n\n2 1\n1 1\n1 2\n2 1\n1 2\n\n5 4\n1 2 3 4 4\n2 3 5 4 2\n5 3 2 4 2\n1 2\n1 3\n1 4\n4 5\n","YES\nYES\nNO\nYES\nNO\n"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}