While Uolevi was practicing this year's edition of the HIIT open programming contest, they tried the Factory problem. As Uolevi is good in graph theory, they immediately realized they need to represent the jobs as a graph. Unfortunately their solution gives WA on some testcases. Help Uolevi understand why.

Uolevi's idea is to, for each node, calculate the longest dependency chain starting from that node. Uolevi will then process the jobs in this order, starting with nodes with the longest dependency chains. He's quite confident his code doesn't have any bugs, but rather a logical error.

Input

• No input

Output

Your program should output a test case where the solution fails.

Constraints (of your output)

• 1 \le n \le 500
• 0 \le m \le \frac{n(n-1)}{2}

Uolevi's code

#include <bits/stdc++.h>
using namespace std;
#define ll long long

vector<vector<ll>> adjList;
ll findPrioritiesDFS(ll node, vector<ll>& jobPriorities, vector<bool>& visited)
{
    if (visited[node])
        return jobPriorities[node];
    
    ll a = 0;
    for (ll kid : adjList[node])
        a = max(a, 1+findPrioritiesDFS(kid, jobPriorities, visited));
    jobPriorities[node] = a;
    visited[node] = true;
    return a;
}
 
int main() {
    ll n, m;
    cin >> n >> m;
 
    adjList = vector<vector<ll>>(n, vector<ll>());
    vector<ll> jobPriorities(n);
 
    vector<ll> dependencies(n, 0);
 
    for (ll i = 0; i < m; i++)
    {
        ll a, b;
        cin >> a >> b;
 
        adjList[a-1].push_back(b-1);
        dependencies[b-1]++;
    }
 
    vector<bool> visited(n, false);
    for (ll i = 0; i < n; i++)
        findPrioritiesDFS(i, jobPriorities, visited);
    
    // {prio, node} of all jobs the machines can do right now
    priority_queue<pair<ll, ll>> pq;
    for (ll i = 0; i < n; i++)
        if (dependencies[i] == 0)
            pq.push({jobPriorities[i], i});
 
    // Always try to do two jobs with the highest priority
    ll count = 0;
    while (!pq.empty())
    {
        count++;
        auto [prio, idx1] = pq.top(); // do one job
        pq.pop();
        if (!pq.empty()) // can we do another job?
        {
            auto [prio2, idx2] = pq.top();
            pq.pop();
            for (ll child : adjList[idx2])
            {
                dependencies[child]--;
                if (dependencies[child] == 0)
                    pq.push({jobPriorities[child], child});
            }
        }
        for (ll child : adjList[idx1])
        {
            dependencies[child]--;
            if (dependencies[child] == 0)
                pq.push({jobPriorities[child], child});
        }
    }
    cout << count;
}