class Solution {
public:
    vector<vector<int>> validArrangement(vector<vector<int>>& pairs) {
        unordered_map<int,vector<int>>graf;
        unordered_map<int,int>nrMuchii;
        unordered_map<int,int>grad;
        vector<vector<int>>output;
        stack<int>stiva;
        vector<int>perechi;

        for(auto p:pairs)
        {
            nrMuchii[p[0]]++;
            graf[p[0]].push_back(p[1]);
            grad[p[0]]++;
            grad[p[1]]--;
        }

        int nr=0;
        for(auto i:grad)
        {
            if(i.second!=0)
            {
                nr++;
                if(i.second>0)
                    stiva.push(i.first);
            }
        }

        if(stiva.empty() == true)
            stiva.push(pairs[0][0]);

        int temp=stiva.top();
        while(stiva.empty() == false)
        {
            if(nrMuchii[temp]!=0)
            {
                nrMuchii[temp]--;
                stiva.push(temp);
                int next=graf[temp].back();
                graf[temp].pop_back();
                temp=next;
            }
            else
            {
                perechi.push_back(temp);
                temp=stiva.top();
                stiva.pop();
            }
        }

        reverse(perechi.begin(), perechi.end());
        for (int i = 0; i < perechi.size() - 1; ++i)
            output.push_back({perechi[i], perechi[i + 1]});
        return output;
    }
};