#include <bits/stdc++.h>
using namespace std;
const int INF=1e9;
int n, d, u;
vector<int> h, a, b;
void init(int N, int D, int H[])
{
n=N;
d=D;
h.resize(n);
for (int i=0; i<n; i++)
h[i]=H[i];
return;
}
void curseChanges(int U, int A[], int B[])
{
u=U;
a.resize(u);
b.resize(u);
for (int i=0; i<u; i++)
a[i]=A[i];
for (int i=0; i<u; i++)
b[i]=B[i];
return;
}
int question(int x, int y, int v)
{
set<int> xtrust, ytrust;
for (int i=0; i<v; i++)
{
if (a[i]==x)
{
if (!xtrust.count(b[i]))
xtrust.insert(b[i]);
else
xtrust.erase(b[i]);
}
if (b[i]==x)
{
if (!xtrust.count(a[i]))
xtrust.insert(a[i]);
else
xtrust.erase(a[i]);
}
if (a[i]==y)
{
if (!ytrust.count(b[i]))
ytrust.insert(b[i]);
else
ytrust.erase(b[i]);
}
if (b[i]==y)
{
if (!ytrust.count(a[i]))
ytrust.insert(a[i]);
else
ytrust.erase(a[i]);
}
}
vector<int> vx, vy;
for (auto t : xtrust)
vx.push_back(h[t]);
for (auto t : ytrust)
vy.push_back(h[t]);
sort(vx.begin(), vx.end());
sort(vy.begin(), vy.end());
if (vx.empty() || vy.empty())
return INF;
int mind=INF;
int j=0;
for (int i=0; i<vx.size(); i++)
{
while (j<vy.size() && vx[i]>vy[j])
j=j+1;
if (j<vy.size())
mind=min(mind, vy[j]-vx[i]);
if (j-1>=0)
mind=min(mind, vx[i]-vy[j-1]);
}
return mind;
}
/*int main()
{
int htemp[]={ 2 , 42 , 1000 , 54 , 68 , 234 };
init(6, 5, htemp );
int atemp[]={ 0 , 2 , 3 , 3 , 3 , 1 , 5 , 0 , 3 , 1 , 3 };
int btemp[]={ 1 , 0 , 4 , 5 , 5 , 3 , 3 , 5 , 0 , 3 , 5 };
curseChanges(11, atemp, btemp) ;
while (true)
{
int x, y, v;
cin >> x >> y >> v;
cout << question(x, y, v) << '\n';
}
return 0;
}*/
