#include <map>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <vector>
#include <numeric>
#include <algorithm>
#include <iostream>
#include <string>
#include <cstring>
#include <sstream>
#include <functional>
#include <queue>
#include <deque>
#include <stack>
#include <cassert>
#include <iomanip>
#include <cmath>
#include <bitset>
using namespace std;
#include "simurgh.h"
using int64 = long long;
int N, M;
vector<vector<int>> eidx;
vector<vector<int>> adj;
vector<int> par;
vector<int> depth;
vector<char> used;
vector<int> status;
vector<int> tree_idx;
vector<int> back_idx;
vector<int> all_idx;
vector<char> added;
int get(int u, int v) {
assert(eidx[u][v] != -1);
return eidx[u][v];
}
void dfs(int n, int p) {
//cerr << n << " " << p << "\n";
used[n] = true;
for (auto v : adj[n]) {
if (v != p) {
int e = get(n, v);
if (!used[v]) {
// Forward edge
par[v] = n;
depth[v] = depth[n] + 1;
tree_idx.push_back(e);
all_idx.push_back(e);
dfs(v, n);
} else if (!added[e]) {
added[e] = true;
back_idx.push_back(e);
all_idx.push_back(e);
}
}
}
}
vector<int> get_cycle(int u, int v) {
vector<int> edges;
auto go_up = [&] (int & el) {
edges.push_back(get(el, par[el]));
el = par[el];
};
while(depth[u] > depth[v]) {
go_up(u);
}
while(depth[u] < depth[v]) {
go_up(v);
}
while(u != v) {
go_up(u);
go_up(v);
}
return edges;
}
std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
auto edge_str = [&](int e) {
return to_string(u[e]) + " - " + to_string(v[e]) + " idx: " + to_string(e);
};
N = n;
M = u.size();
adj.resize(N, vector<int>{});
eidx.resize(N, vector<int>(N, -1));
par.resize(N, -1);
used.resize(N, 0);
depth.resize(N, 0);
status.resize(M, -1);
added.resize(M, 0);
for (int i = 0; i < M; i++) {
eidx[ u[i] ][ v[i] ] = eidx[ v[i] ][ u[i] ] = i;
adj[ u[i] ].push_back( v[i] );
adj[ v[i] ].push_back( u[i] );
}
// 1. Find DFS tree
dfs(0, 0);
assert(tree_idx.size() == N - 1);
assert(tree_idx.size() + back_idx.size() == M);
assert(all_idx.size() == M);
// cerr << "tree edges:\n";
for (auto e : tree_idx) {
// cerr << edge_str(e) << "\n";
assert(status[e] == -1);
}
// 50 points
int tree_ans = count_common_roads(tree_idx);
// cerr << "tree_ans: " << tree_ans << "\n";
for (auto e : back_idx) {
// get cycle
auto cycle = get_cycle(u[e], v[e]);
int unknown = 0;
for (auto c : cycle)
unknown += (status[c] == -1);
// cerr << "Back edge: " << edge_str(e) << "\n";
// cerr << "cycle\n";
// for (auto c : cycle) {
// cerr << edge_str(c) << "\n";
// }
auto replace = [] (int e, int c, vector<int>& query) {
auto p = find(query.begin(), query.end(), c);
assert(p != query.end());
*p = e;
};
auto replace_and_query = [&] (int e, int c) {
auto query = tree_idx;
replace(e, c, query);
return count_common_roads(query) - tree_ans;
};
if (!unknown) { // all is known
// cerr << "all known\n";
// Just 1 query needed
status[e] = replace_and_query(e, cycle[0]) + status[cycle[0]];
} else if (unknown < cycle.size()) { // at least one is known
// cerr << "at least one is known\n";
// <= C++14
int cand = -1;
for (auto c : cycle) {
if (status[c] != -1) {
cand = c;
break;
}
}
status[e] = replace_and_query(e, cand) + status[cand];
// use this to find the unknowns
for (auto c : cycle) {
if (status[c] == -1) {
status[c] = -replace_and_query(e, c) + status[e];
}
}
} else { // all is unknown
// cerr << "all is unknown\n";
int neg = 0;
int pos = 0;
for (auto c : cycle) {
status[c] = replace_and_query(e, c);
// cerr << edge_str(c) << " delta: " << status[c] << "\n";
neg += (status[c] < 0);
pos += (status[c] > 0);
}
if (!pos && !neg) {
// cerr << "nothing is different\n";
assert (!pos);
assert (!neg);
for (auto c : cycle) {
status[c] = 0;
}
status[e] = 0;
} else {
assert(!pos || !neg);
if (pos) {
for (auto c : cycle) {
status[c] = 1 - status[c];
}
status[e] = 1;
// cerr << "positive e\n";
} else {
for (auto c : cycle) {
status[c] = -status[c];
}
status[e] = 0;
// cerr << "negative e\n";
}
// cerr << "find out\n";
// for (auto c : cycle) {
// cerr << edge_str(c) << " -> " << status[c] << "\n";
// }
// cerr << "\n";
}
}
}
vector<int> res;
int rem_unknown = 0;
int rem_good = 0;
for (auto e : all_idx) {
if (status[e] == -1) {
rem_unknown++;
res.push_back(e);
} else if (status[e] == 1) {
rem_good++;
res.push_back(e);
}
}
assert(rem_good + rem_unknown == N - 1);
return res;
}
