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;
      }
      				
      			

      0 Comments

      Leave a Reply

      Avatar placeholder

      Your email address will not be published.