CSES - HIIT Open 2019 - Results
 Task: Many Cycles Sender: bigint bugaa Submission time: 2019-05-25 12:32:05 +0300 Language: C++ Status: READY Result: ACCEPTED
Test results
testverdicttime
#1ACCEPTED0.05 sdetails
#2ACCEPTED0.02 sdetails

### Code

```#include <iostream>
#include <queue>
#include <utility>
using namespace std;
using ll = long long;
const int INF = 1e9 + 7;

// 4 5
// 1 2
// 1 3
// 1 4
// 2 3
// 3 4

const int N = 1e5;
vector<pair<int, int>> conns[N];
int ind[N];

int dfs(int i, int pe, int ci) {
// cerr << "dfs to " << i << ' ' << pe << ' ' << ci << '\n';
int res = INF;
ind[i] = ci;
++ci;

for (auto pr : conns[i]) {
if (pr.second == pe) continue;
int t = pr.first;

// cerr << t << ' ' << ind[t] << '\n';
int sub = INF;
if (ind[t] != INF) {
sub = ind[t];
} else {
// cerr << " call with " << t << ' ' << pr.second << ' ' << ci << '\n';
sub = dfs(t, pr.second, ci);
}
if (sub == -2) return -2;
if (sub != INF && sub <= ind[i]) {
if (res != INF) return -2;
res = sub;
}
}
// cerr << i << ' ' << pe << ' ' << ci << ": " << res << '\n';
return (res < ind[i] ? res : INF);
}

void solve() {
int n, m;
cin >> n >> m;
for (int i = 0; i < n; ++i) {
conns[i].clear();
ind[i] = INF;
}
for (int j = 0; j < m; ++j) {
int a, b;
cin >> a >> b;
--a; --b;
conns[a].push_back({b, j});
conns[b].push_back({a, j});
}

bool fail = false;
for (int i = 0; i < n; ++i) {
if (ind[i] == INF) {
int sub = dfs(i, -1, 0);
if (sub == -2) fail = true;
}
}
if (fail) cout << "YES\n";
else cout << "NO\n";
}

int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);

int t;
cin >> t;
for (int ti = 0; ti < t; ++ti) solve();
}
```

### Test details

#### Test 1

Verdict: ACCEPTED

input
1000
100 78
97 68
75 90
58 80
...

correct output
YES
YES
YES
YES
NO
...

user output
YES
YES
YES
YES
NO
...
Truncated

#### Test 2

Verdict: ACCEPTED

input
11
2 1
1 2
6 6
1 2
...

correct output
NO
NO
NO
YES
YES
...

user output
NO
NO
NO
YES
YES
...