#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<algorithm>
#include<limits.h>
#include<math.h>
#include<map>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<iomanip>
#include<cstring>
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
using namespace std;
void solve(){
int n,m;
cin>>n>>m;
vector<int>nxt(2e6,-1);
vector<bool>vis(2e6);
for(int i=0;i<n;i++){
int a,b;
cin>>a>>b;
a--;b--;
nxt[a]=b+1;
nxt[b]=a+1;
}
priority_queue<int>q;
int ms=-1;
for(int i=0;i<2e6;i++){
if(vis[i])
continue;
int curr=i;
int size=0;
while(curr<2e6&&!vis[curr]){
vis[curr]=true;
if(nxt[curr]==-1)
curr++;
else{
curr=nxt[curr];
size++;
}
}
if(ms==-1)
ms=size;
else
q.push(size);
}
while(m&&q.size()){
ms+=q.top()+2;
m--;
q.pop();
}
cout<<ms+m+m/2*2<<"\n";
}
int main(){
ios::sync_with_stdio(false);cout.tie(NULL);cin.tie(NULL);
//freopen("input.in","r",stdin);freopen("output.out","w",stdout);
int t=1;//cin>>t;
while(t--)solve();
return 0;
}
/*
3
1
10 11
1 4
2 3
6
3
3
5 7
6 10
1999999 2000000
12
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
8540 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
8540 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
8540 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
8536 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
8536 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
8536 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
8536 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
8536 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
8536 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
8540 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
8540 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
8540 KB |
Output is correct |
2 |
Correct |
10 ms |
8540 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
8536 KB |
Output is correct |
2 |
Correct |
10 ms |
8540 KB |
Output is correct |
3 |
Correct |
12 ms |
8868 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
8540 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
8540 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
8780 KB |
Output is correct |
2 |
Correct |
61 ms |
13396 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
46 ms |
9172 KB |
Output is correct |
2 |
Correct |
85 ms |
9168 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
160 ms |
10700 KB |
Output is correct |
2 |
Correct |
134 ms |
10580 KB |
Output is correct |
3 |
Correct |
209 ms |
26316 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
227 ms |
10852 KB |
Output is correct |
2 |
Correct |
157 ms |
24528 KB |
Output is correct |
3 |
Correct |
150 ms |
22868 KB |
Output is correct |
4 |
Correct |
150 ms |
22864 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
179 ms |
14276 KB |
Output is correct |
2 |
Correct |
194 ms |
27588 KB |
Output is correct |
3 |
Correct |
178 ms |
28088 KB |
Output is correct |
4 |
Correct |
158 ms |
28220 KB |
Output is correct |