#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define bit(n,i) ((n>>i)&1)
#define all(x) x.begin(),x.end()
#define int long long
typedef long long ll;
typedef pair<int,int> pii;
typedef double ld;
typedef pair<ld,ld> pdd;
typedef pair<ll,ll> pll;
const ll maxn=2e5+5;
const ll offset=2e5;
const ll inf=1e18;
const int base=350;
const ll mod=998244353;
int n,q,a,b,k;
struct Edge
{
int u,v,w;
bool operator <(const Edge& o) const
{
return w<o.w;
}
}ea[maxn],eb[maxn];
struct Event
{
int u,v,v1;
};
int par[2][maxn];
vector<int> L[2][maxn];
vector<Event> trace[maxn];
int Find(int id,int u)
{
return par[id][u]<0?u:par[id][u]=Find(id,par[id][u]);
}
int cur=0,ans=inf;
map<pii,int> cnt;
int Get(int u) {return u*(u-1)/2;}
void Update(int u,int val)
{
cur+=Get(cnt[{Find(0,u),Find(1,u)}]);
cnt[{Find(0,u),Find(1,u)}]+=val;
cur-=Get(cnt[{Find(0,u),Find(1,u)}]);
// cerr<<"Add "<<u<<' '<< Find(0,u) <<' '<<Find(1,u)<<' '<<val<<'\n';
}
void Union(int id,int u,int v,int idd)
{
if ((u=Find(id,u))==(v=Find(id,v))) return;
// cerr<< "Merge "<<id<<' '<<u<<' '<<v<<'\n';
if (par[id][u]>par[id][v]) swap(u,v);
cur-=Get(-par[id][u]);
cur-=Get(-par[id][v]);
par[id][u]+=par[id][v];
// if (id==1) cerr<< "trace "<<idd<<' '<<u<<' '<<par[id][4]<<' '<<4<<'\n';
for(int v1:L[id][v])
{
if (v1==v) continue;
L[id][u].pb(v1);
Update(v1,-1);
// if (id==1) cerr<< "trace "<<idd<<' '<<u<<' '<<par[id][v1]<<' '<<v1<<'\n';
if (id==1)
{
trace[idd].pb({u,par[id][v1],v1});
}
par[id][v1]=u;
Update(v1,1);
}
L[id][u].pb(v);
Update(v,-1);
if (id==1)
{
trace[idd].pb({u,par[id][v],v});
}
par[id][v]=u;
Update(v,1);
cur+=Get(-par[id][u]);
L[id][v].clear();
}
void clear()
{
cur=0;
cnt.clear();
for1(id,0,1) for1(i,1,n)
{
par[id][i]=-1;
L[id][i].clear();
L[id][i].pb(i);
}
for1(i,1,n) Update(i,1);
}
int pre[2][maxn];
void sol()
{
cin >> n>>a>>b>>k;
for1(i,1,a) cin >> ea[i].u>> ea[i].v>>ea[i].w;
for1(i,1,b) cin >> eb[i].u>> eb[i].v>>eb[i].w;
sort(ea+1,ea+1+a);
sort(eb+1,eb+1+b);
clear();
for1(i,1,a)
{
Union(0,ea[i].u,ea[i].v,i);
if (cur>=k)
{
ans=min(ans,ea[i].w);
break;
}
}
// cerr<< "reset:\n";
clear();
for1(i,1,b)
{
// cerr<< "Merge "<<"1 "<<eb[i].u<<' '<<eb[i].v<<'\n';
Union(1,eb[i].u,eb[i].v,i);
// if (i==2)
// {
// for(auto x: L[1][1])
// {
// cerr<<"gg "<< x<<'\n';
// }
// }
for(Event& x:trace[i])
{
if (x.v<0) swap(x,trace[i].back());
}
if (cur>=k)
{
ans=min(ans,eb[i].w);
break;
}
}
// cerr<< cur<<'\n';
int j=b;
for1(i,1,a)
{
// cerr<< "Merge "<<"0 "<<ea[i].u<<' '<<ea[i].v<<'\n';
Union(0,ea[i].u,ea[i].v,i);
// cerr<< i<<' '<<cur<<'\n';
// if (cur<k) continue;
// for1(i,1,n) cerr<<"gg "<< Find(0,i)<<' '<<Find(1,i)<<'\n';
// cerr<< i<<' '<<j<<' '<<cur<<'\n';
while (cur>=k && j>=1)
{
// cerr<< "Rollback "<<"1 "<<eb[j].u<<' '<<eb[j].v<<'\n';
for(Event x:trace[j])
{
int u=x.u,v=x.v,v1=x.v1;
Update(v1,-1);
par[1][v1]=v;
// cerr<< v1<<" -> "<<v<<'\n';
if (v<0)
{
cur+=Get(-par[1][v1]);
cur-=Get(-par[1][u]);
par[1][u]-=v;
cur+=Get(-par[1][u]);
}
}
for(Event x:trace[j]) Update(x.v1,1);
j--;
}
// for1(i,1,n) cerr<<"gg "<< Find(0,i)<<' '<<Find(1,i)<<'\n';
// cerr<< i<<' '<<j<<' '<<cur<<'\n';
// if (cur>=k) ans=min(ans,pre[1][i]);
if (j<b) ans=min(ans,ea[i].w+eb[j+1].w);
}
if (ans!=inf) cout << ans;
else cout << -1;
}
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// freopen("propagation.inp","r",stdin);
// freopen("propagation.out","w",stdout);
int t=1;//cin >> t;
while (t--) {
sol();
}
}
/*
6 7 2 7
4 6 2
3 5 3
3 3 2
5 6 6
4 6 2
1 1 1
3 3 7
1 5 48
5 6 10
5 2 5 5
2 5 6
1 5 8
1 1 11
1 4 42
3 4 47
2 4 38
3 5 36
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
14428 KB |
Output is correct |
2 |
Incorrect |
6 ms |
14464 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
729 ms |
72772 KB |
Output is correct |
2 |
Correct |
451 ms |
66496 KB |
Output is correct |
3 |
Correct |
199 ms |
51788 KB |
Output is correct |
4 |
Incorrect |
6 ms |
14428 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
6 ms |
14440 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
14428 KB |
Output is correct |
2 |
Incorrect |
6 ms |
14464 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |