#include<bits/stdc++.h>
const int maxn = 1e5+1;
const int maxm = 2e5+1;
using namespace std;

vector<int> adj[maxn];
queue<int> q;
bool avail[maxn];
int trace[maxn];
int diff[maxm];
int minDiff;
int n,m,maxx;
int l = 1;
int h;

void addEdge(int u, int v)
{
    adj[u].push_back(v);
    adj[v].push_back(u);
}

void visit(int u, int mid)
{
    avail[u] = false;
    cout << u << endl;
    for(int v : adj[u])
    {
        cout << abs(diff[u] - diff[v]) << " " << mid << endl;
        if(avail[v] && abs(diff[u]-diff[v]) <= mid)
        {
            trace[v] = u;
            visit(v,mid);
        }
    }
}

void solve()
{
    //cout << maxx << endl;
    int mid;
    l = 1;
    h = maxx;
    while(l <= h)
    {
        mid = (l+h)/2;
        fill(avail,avail+n,true);
        visit(1,mid);
        cout << l << " " << h << " " << mid << " " << avail[n] << endl;
        if(avail[n-1]==false)
        {
            minDiff = mid;
            h = mid - 1;
        }
        else
            l = mid + 1;
    }
    cout << minDiff;
}

int main()
{
    //freopen("wildlife.inp","r",stdin);
    int u,v;
    cin >> n >> m;
    for(int i = 1; i <= n; ++i)
        cin >> diff[i];
    for(int i = 1; i <= m; ++i)
    {
        cin >> u >> v;
        addEdge(u,v);
    }
    for(int i = 1; i < n; ++i)
        maxx = max(diff[i],diff[i+1]);
    solve();