## Strict Permutation Codechef Problem Solution | STRPERM

You are given an integer . You have to find a permutation of the integers that satisfies conditions of the following form:

• , denoting that the element must appear in the prefix of length . Formally, if the index of the element is (i.e, ), then the condition must hold.

Print -1 if no such permutation exists. In case multiple permutations that satisfy all the conditions exist, find the lexicographically smallest one.

Note: If two arrays and have the same length , then is called lexicographically smaller than only if there exists an index such that

.

### Input Format

• The first line of input will contain a single integer , denoting the number of test cases.
• The first line of each test case contains two space-separated integers and – the length of permutation and the number of conditions to be satisfied respectively.
• The next lines describe the conditions. The -th of these lines contains two space-separated integers and

### Output Format

For each test case, output a single line containing the answer:

• If no permutation satisfies the given conditions, print −1.
• Otherwise, print space-separated integers, denoting the elements of the permutation. If there are multiple answers, output the lexicographically smallest one.

### Constraints

• for each
• The sum of over all test cases won’t exceed

### Sample Input 1

4
3 2
2 1
1 2
4 3
1 2
4 1
3 2
4 1
2 3
5 2
5 4
3 2


### Sample Output 1

2 1 3
-1
1 2 3 4
1 3 2 5 4


### Explanation

Test case : The only permutation of length that satisfies all the conditions is

Test case : There is no permutation of length that satisfies all the given conditions.

Test case : There are many permutations of length that satisfy all the conditions, such as , etc. is the lexicographically smallest among them.

				
using namespace std;

int main() {
int T;
cin >> T;
while(T--){
int n,m;
cin >> n >> m;
vector<int>v[n+1];
unordered_map<int,int>ff;
for(int i=0;i<m;i++){
int x,y;
cin >> x >> y;
v[y].push_back(x);
ff[x]++;
}
for(int i=1;i<=n;i++){
if(ff[i])continue;
v[n].push_back(i);
}
vector<int>ans;
priority_queue<int>pq;
for(int i=n;i>=1;i--){
for(auto j:v[i])pq.push(j);
if(pq.empty()){
cout << -1 << endl;
break;
}
ans.push_back(pq.top());
pq.pop();
}
if(ans.size()<n)continue;
for(int i=0;i<n;i++)cout << ans[n-i-1] << " ";
cout << endl;
}
return 0;
}