# CPP Program Permutation Swaps – Advanced Graphs

• Kevin has a permutation P of N integers 1, 2, …, N, but he doesn’t like it. Kevin wants to get a permutation Q.
• Also, he believes that there are M good pairs of integers (ai, bi). Kevin can perform the following operation with his permutation:
• Swap Px and Py only if (x, y) is a good pair.
• Help him and tell if Kevin can obtain permutation Q using such operations.

Input format:

• The first line of input will contain an integer T, denoting the number of test cases.
• Each test case starts with two space-separated integers N and M. The next line contains N space-separated integers Pi. The next line contains N space-separated integers Qi. Each of the next M lines contains two space-separated integers ai and bi.

Output format:

• For every test case output “YES” (without quotes) if Kevin can obtain permutation Q and “NO” otherwise.

Constraints:

1 ≤ T ≤ 10
2 ≤ N ≤ 100000
1 ≤ M ≤ 100000
1 ≤ Pi, Qi ≤ N. Pi and Qi are all distinct.
1 ≤ ai < bi ≤ N

Sample Input:

```2
4 1
1 3 2 4
1 4 2 3
3 4
4 1
1 3 2 4
1 4 2 3
2 4```

Sample Output:

```.wp-block-code {
border: 0;
}

.wp-block-code > span {
display: block;
overflow: auto;
}

.shcb-language {
border: 0;
clip: rect(1px, 1px, 1px, 1px);
-webkit-clip-path: inset(50%);
clip-path: inset(50%);
height: 1px;
margin: -1px;
overflow: hidden;
position: absolute;
width: 1px;
word-wrap: normal;
word-break: normal;
}

.hljs {
box-sizing: border-box;
}

.hljs.shcb-code-table {
display: table;
width: 100%;
}

.hljs.shcb-code-table > .shcb-loc {
color: inherit;
display: table-row;
width: 100%;
}

.hljs.shcb-code-table .shcb-loc > span {
display: table-cell;
}

.wp-block-code code.hljs:not(.shcb-wrap-lines) {
white-space: pre;
}

.wp-block-code code.hljs.shcb-wrap-lines {
white-space: pre-wrap;
}

.hljs.shcb-line-numbers {
border-spacing: 0;
counter-reset: line;
}

.hljs.shcb-line-numbers > .shcb-loc {
counter-increment: line;
}

.hljs.shcb-line-numbers .shcb-loc > span {
}

.hljs.shcb-line-numbers .shcb-loc::before {
border-right: 1px solid #ddd;
content: counter(line);
display: table-cell;
text-align: right;
-webkit-user-select: none;
-moz-user-select: none;
-ms-user-select: none;
user-select: none;
white-space: nowrap;
width: 1%;
}
```NO
YES``````

## Code:

``````#include<iostream>
#include<vector>
#include<unordered_set>
#include<iterator>
using namespace std;
void dfs(vector<int>*edges, int start, bool*visited, unordered_set<int>*component)
{
if(visited[start])
{
return;
}
visited[start]=true;
component->insert(start);
for(vector<int>::iterator it=edges[start].begin(); it!=edges[start].end(); it++)
{
if(!visited[*it])
{
dfs(edges, *it, visited, component);
}
}
}
unordered_set<unordered_set<int>*>* getComponents(vector<int>*edges, int n)
{
bool *visited=new bool[n];
for(int i=0; i<n; i++)
{
visited[i]=false;
}
unordered_set<unordered_set<int>*>*output=new unordered_set<unordered_set<int>*>();
for(int i=0; i<n; i++)
{
if(!visited[i])
{
unordered_set<int>*component=new unordered_set<int>();
dfs(edges, i, visited, component);
output->insert(component);
}
}
return output;
}
int main()
{
int t;//test cases
cin>>t;
while(t--)
{
int n, m;
cin>>n>>m;
int *p=new int [n];
int *q=new int [n];
for(int i=0; i<n; i++)
{
cin>>p[i];
}
for(int i=0; i<n; i++)
{
cin>>q[i];
}

//graph initiated
vector<int>*edges=new vector<int>[n];
for(int i=0; i<m; i++)
{
int a, b;
cin>>a>>b;
edges[a-1].push_back(b-1);
edges[b-1].push_back(a-1);
}
unordered_set<unordered_set<int>*>* components=getComponents(edges, n);

unordered_set<unordered_set<int>*>::iterator it1=components->begin();
bool flag=true;
while(it1!=components->end())
{
unordered_set<int>*component=*it1;
unordered_set<int>::iterator it2=component->begin();
unordered_set<int>p_index_set;
unordered_set<int>q_index_set;
while(it2!=component->end())
{
p_index_set.insert(p[*it2]);
q_index_set.insert(q[*it2]);
it2++;
}
if(p_index_set!=q_index_set)
{
flag=false;
}
it1++;
}
if(flag)
{
cout<<"YES"<<endl;
}
else
{
cout<<"NO"<<endl;
}
}
return 0;
}
```Code language: C++ (cpp)```