#include <bits/stdc++.h>
#define int long long
#define ll long long
#define pb push_back
#define fi first
#define se second
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
#define ld long double
using namespace std;
typedef pair<int,int> pii;
typedef pair<char,char> pcc;
typedef pair<pii,int> ipii;
typedef pair<pii,pii> ipiii;
const int MAXN = 3e5+10;
const int SQRT = 300;
const int MAXA = 50;
const int LOG = 20;
const int INF = 1e18+10;
const ld EPS = 1e-6;
const int MOD = 998244353;
int sum(int a, int b){ return (a+b)%MOD; }
void chsum(int &a, int b){ a = (a+b)%MOD; }
void chsub(int &a, int b){ a = (a+MOD-b)%MOD; }
int mul(int a, int b){ return (a*b)%MOD; }
void chmul(int &a, int b){ a = (a*b)%MOD; }
void chmn(int &a, int b){ a = min(a, b); }
void chmx(int &a, int b){ a = max(a, b); }
int n, m;
vector <int> adj[MAXN];
int mx=0;
void dfs(int nw, int par, int dis){
chmx(mx, dis);
for(auto nx : adj[nw]){
if(nx==par) continue;
dfs(nx,nw,dis+1);
}
}
bool solve(){
if(m!=n-1) return 0;
bool can = 1;
for(int i=1; i<=n; i++){
int cnt = 0;
for(auto nx : adj[i]){
mx=0;
dfs(nx,i,1);
if(mx>=3) cnt++;
}
if(cnt>=3) can = 0;
}
return can;
}
signed main(){
// ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n>>m;
for(int i=1; i<=m; i++){
int x, y; cin>>x>>y;
adj[x].pb(y); adj[y].pb(x);
}
if(solve()) cout << "YES\n";
else cout << "NO\n";
}
/*
if(m==n-1){
int num = 0, id = -1;
for(int i=1; i<=n; i++)
if(adj[i].size() >= 3) num++, id = i;
if(num>=2){
cout << "NO\n"; exit(0);
} else if(num==1){
bool can = 1;
for(int i=1; i<=n; i++){
if(i == id) continue;
if(adj[i].size() >= 2) can = 0;
}
if(can){
cout << "YES\n2\n"; cout<<id<<' '<<id<<'\n';
} else cout << "NO\n";
exit(0);
}
if(n==1){
cout << "YES\n1\n1\n";
exit(0);
}
if(n<=3){
cout << "YES\n2\n2 2\n"; exit(0);
}
cout << "YES\n";
cout << 2*(n-2) << '\n';
for(int i=2; i<=n-1; i++) cout << i << ' ';
for(int i=n-1; i>=2; i--) cout << i << ' ';
cout << '\n';
} else {
cout << "NO\n";
}
*/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |