https://www.codechef.com/viewsolution/44151364
#include <bits/stdc++.h>
using namespace std;
std::vector<int>path[100001];
void dfs(int kya , int current , int visited[] , int n){
visited[current]=kya;
for(int i=0;i<path[current].size();i++){
if(visited[path[current][i]]==-1){
dfs(kya,path[current][i],visited,n);
}
}
}
int main() {
int t;std::cin >> t;
while(t--){
for(int i=0;i<=100000;i++){
path[i].clear();
}
int n,m;std::cin >> n>>m;
int arr[n+1];
for(int i=1;i<=n ; i++){
cin>>arr[i];
}
for(int i=0;i<m;i++){
int x,y;std::cin >> x>>y;
path[x].push_back(y);
path[y].push_back(x);
}
int visited[n+1];
for(int i=1;i<=n;i++){
visited[i]=-1;
}
int hi=0;
for(int i=1;i<=n;i++){
if(visited[i]==-1){
dfs(hi,i,visited,n);
hi++;
}
}
// for(int i=1;i<=n;i++)
// {
// cout<<visited[i]<<" ";
// }
// cout<<"\n";
// std::cout << hi << std::endl;
std::vector<int>indexes[hi];
for(int i=1;i<=n;i++){
indexes[visited[i]].push_back(i);
}
std::vector<int>values[hi];
for(int i=1;i<=n;i++){
values[visited[i]].push_back(arr[i]);
}
for(int i=0;i<hi;i++){
sort(values[i].begin(),values[i].end());
}
bool isit=true;
for(int i=0;i<hi;i++){
//cout<<"hi "<<i<<"\n";
for(int j=0;j<values[i].size();j++){
//cout<<indexes[i][j]<<" "<<values[i][j]<<"\n";
if(indexes[i][j]!=values[i][j]){
isit=false; break;
}
}
if(isit==false){
break;
}
}
if(isit){
std::cout << "Possible\n";
}
else{
cout<<"Impossible\n";
}
// cout<<"done\n";
/* for(int i=0;i<hi;i++){
for(int j=0;j<indexes[hi].size();j++){
arr[indexes[hi][j]]=values[hi][j];
}
}
bool yes=true;
for(int i=1;i<=n;i++){
if(arr[i]!=i){
yes=false;break;
}
}
if(yes){
std::cout << "Possible\n";
}
else{
cout<<"Impossible\n";
}*/
}
return 0;
}