//Coded by Chirath Nirodha
#include<bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//using namespace __gnu_pbds;
using namespace std;
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define P push
#define I insert
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
//typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;
const ll mod=1e9+7;
inline void io(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
const int MAXN=100000;
vector<int> v[MAXN];
int parent[MAXN];
bool visited[MAXN];
vector<int> cyc;
vector<int> chil[MAXN];
ll dp[MAXN][2][2][2][2];
int rt,sp;
bool foundcy=false;
void dfs(int x){
if(visited[x]){
if(foundcy)return;
foundcy=true;
int cur=parent[x];
cyc.PB(x);
while(cur!=x){
cyc.PB(cur);
cur=parent[cur];
}
return;
}
visited[x]=true;
for(int i=0;i<v[x].size();i++){
if(parent[x]==v[x][i])continue;
parent[v[x][i]]=x;
dfs(v[x][i]);
}
}
ll rec(int a,int b,int c,int x,int y){
if(dp[a][b][c][x][y]!=-1)return dp[a][b][c][x][y];
bool ok=true;
if(a==rt && b!=x)ok=false;
if(a==sp && b!=y)ok=false;
if(a==sp && c && x)ok=false;
if(!ok)return dp[a][b][c][x][y]=INT64_MAX;
int cov=0;
if(c)cov++;
if(a==rt && y)cov++;
if(a==sp && x)cov++;
ll tt=0;
vector<int> unst;
for(int i=0;i<chil[a].size();i++){
ll dd=rec(chil[a][i],0,b,x,y);
if(dd!=INT64_MAX)tt+=dd;
else unst.PB(i);
}
if(unst.size()>1 || cov>0)return dp[a][b][c][x][y]=INT64_MAX;
if(b)tt++;
if(cov>0)dp[a][b][c][x][y]=tt;
else{
ll best=INT64_MAX;
if(unst.size()==1){
ll temp=rec(chil[a][unst[0]],1,b,x,y);
ll dd=rec(chil[a][unst[0]],0,b,x,y);
if(temp!=INT64_MAX && dd!=INT64_MAX)best=min(best,temp-dd);
}
else{
for(int i=0;i<chil[a].size();i++){
ll temp=rec(chil[a][i],1,b,x,y);
ll dd=rec(chil[a][i],0,b,x,y);
if(temp!=INT64_MAX && dd!=INT64_MAX)best=min(best,temp-dd);
}
}
if(best==INT64_MAX)dp[a][b][c][x][y]=best;
else dp[a][b][c][x][y]=tt+best;
}
return dp[a][b][c][x][y];
}
void solve(){
io();
int n;cin>>n;
for(int i=0;i<n;i++){
int a,b;cin>>a>>b;a--;b--;
v[a].PB(b);v[b].PB(a);
}
memset(parent,-1,sizeof(parent));
parent[0]=0;
dfs(0);
rt=cyc[0];sp=cyc[1];
queue<int> q;q.P(rt);
memset(parent,-1,sizeof(parent));
parent[rt]=rt;
while(!q.empty()){
int c=q.front();q.pop();
for(int i=0;i<v[c].size();i++){
int x=v[c][i];
if(x==parent[c] || (x==rt && c==sp) || (x==sp && c==rt))continue;
chil[c].PB(x);
parent[x]=c;
q.P(x);
}
}
memset(dp,-1,sizeof(dp));
ll ans=INT64_MAX;
for(int i=0;i<=1;i++){
for(int j=0;j<=1;j++){
ll temp=rec(rt,i,0,i,j);
ans=min(ans,temp);
}
}
if(ans==INT64_MAX)cout<<-1<<endl;
else cout<<ans<<endl;
}
int main(){
io();
solve();
//int t;cin>>t;for(int i=0;i<t;i++)solve();
return 0;
}
Compilation message
Main.cpp: In function 'void dfs(int)':
Main.cpp:45:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
45 | for(int i=0;i<v[x].size();i++){
| ~^~~~~~~~~~~~
Main.cpp: In function 'll rec(int, int, int, int, int)':
Main.cpp:68:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
68 | for(int i=0;i<chil[a].size();i++){
| ~^~~~~~~~~~~~~~~
Main.cpp:84:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
84 | for(int i=0;i<chil[a].size();i++){
| ~^~~~~~~~~~~~~~~
Main.cpp: In function 'void solve()':
Main.cpp:111:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
111 | for(int i=0;i<v[c].size();i++){
| ~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
17972 KB |
Output is correct |
| 2 |
Incorrect |
8 ms |
17876 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
17876 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
17876 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
17972 KB |
Output is correct |
| 2 |
Incorrect |
8 ms |
17876 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
