class Solution {
    unordered_map<int,bool>mp;
    int ul=4001; //no real proof on upperlimit( might be wrong. please provide insight), but going too many jumps forward and then backwards to reach home can be equivalent to jumping forward and backward alternately! SO do not need to have more than these many nodes.
public:
    void populate(vector<int>adj[],vector<bool>&vis,int i,int &a,int &b)//,int &x,bool back)
    {
        for(i=0;i<ul;i++)
        {
            if(i+a<ul && mp.find(i+a)==mp.end())
                adj[i].push_back(i+a);
            if(i-b>=0 && mp.find(i-b)==mp.end())
                adj[i].push_back(i-b);
        }
    }
    int bfs(vector<int>adj[],vector<bool>&vis,int &a,int &b,int &x)
    {
        queue<pair<int,bool>>q;
        int step=0,num_now=0,num_next=1;
        q.push({0,false});
        while(!q.empty())
        {
            step++;
            num_now=num_next;
            num_next=0;
            
            while(num_now--)
            {
                int temp=q.front().first; //temp=current node
                bool back=q.front().second;//back => did i reach temp using a backward jump?
                q.pop();
                if(temp==x)
                    return step-1;
                for(int i=0;i<adj[temp].size();i++)
                {
                    int neigh=adj[temp][i];
                    if(!vis[neigh] && (neigh==temp+a or (neigh==temp-b && !back)))//if neighbour awaits forward jump,go for it , if backward jump? check if back false or not
                    {  
                        vis[neigh]=true;
                        q.push({neigh,neigh==temp-b});
                        num_next++;
                    }
                }
            }
            
        }
        return -1;
    }
    int minimumJumps(vector<int>& forbidden, int a, int b, int x) {
        
        vector<int>adj[ul];
        vector<bool>vis(ul,false); 
        int n=forbidden.size();
        for(int i=0;i<n;i++)//mapping forbidden nodes for quick access
            mp[forbidden[i]]=true;
        
        populate(adj,vis,0,a,b);//,x,false);
        // for(int i=0;i<ul;i++)
        //     vis[i]=false;
        
        n=bfs(adj,vis,a,b,x);
        mp.clear();
        return n;
    }
};