結果
| 問題 |
No.922 東北きりきざむたん
|
| コンテスト | |
| ユーザー |
 EgorKulikov
|
| 提出日時 | 2019-11-08 22:59:54 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
RE
|
| 実行時間 | - |
| コード長 | 26,814 bytes |
| コンパイル時間 | 2,914 ms |
| コンパイル使用メモリ | 208,888 KB |
| 実行使用メモリ | 48,276 KB |
| 最終ジャッジ日時 | 2024-09-15 02:07:50 |
| 合計ジャッジ時間 | 14,931 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 RE * 3 |
| other | AC * 1 RE * 25 |
ソースコード
/**
* code generated by JHelper
* More info: https://github.com/AlexeyDmitriev/JHelper
* @author Egor Kulikov
*/
#include <iostream>
#include <fstream>
#ifndef JHELPER_EXAMPLE_PROJECT_INPUT_H
#define JHELPER_EXAMPLE_PROJECT_INPUT_H
//
// Created by egor on 30.10.2019.
//
#ifndef JHELPER_EXAMPLE_PROJECT_GENERAL_H
#define JHELPER_EXAMPLE_PROJECT_GENERAL_H
#include <bits/stdc++.h>
using namespace std;
#define all(v) (v).begin(), (v).end()
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
const int MAX_INT = 2147483647;
const double PI = atan(1) * 4;
const int DX_KNIGHT[] = {2, 1, -1, -2, -2, -1, 1, 2};
const int DY_KNIGHT[] = {1, 2, 2, 1, -1, -2, -2, -1};
const int DX4[] = {1, 0, -1, 0};
const int DY4[] = {0, 1, 0, -1};
bool isValidCell(int x, int y, int rows, int cols) {
return x >= 0 && y >= 0 && x < rows && y < cols;
}
void decreaseByOne() {
}
template <typename T, class...Vargs>
void decreaseByOne(vector<T>& arr, Vargs&...arrs) {
for (int& i : arr) {
i--;
}
decreaseByOne(arrs...);
}
template <typename T>
T minim(T& was, T cand) {
return was = min(was, cand);
}
template <typename T>
T maxim(T& was, T cand) {
return was = max(was, cand);
}
inline int bitCount(int number) {
return __builtin_popcount(number);
}
inline int bitCount(ll number) {
return __builtin_popcount(number);
}
#endif //JHELPER_EXAMPLE_PROJECT_GENERAL_H
class Input {
public:
enum ErrorType {
OK,
END_OF_FILE,
UNEXPECTED_SYMBOL,
INVALID_CALL
};
private:
istream& in;
bool exhausted = false;
ErrorType error = OK;
int get();
template<typename T> T readInteger();
int skipWhitespace();
public:
Input(istream& in);
int readInt();
ll readLong();
string readString();
vector<int> readIntArray(int size);
template<typename T> T readType();
template<typename T, typename U> pair<T, U> readType();
template<typename T> vector<T> readArray(int size);
template<typename T1, typename T2> tuple<vector<T1>, vector<T2> > readArrays(int size);
template<typename T1, typename T2, typename T3> tuple<vector<T1>, vector<T2>, vector<T3> > readArrays(int size);
template<typename T1, typename T2, typename T3, typename T4>
tuple<vector<T1>, vector<T2>, vector<T3>, vector<T4> > readArrays(int size);
template<typename T1, typename T2, typename T3, typename T4, typename T5>
tuple<vector<T1>, vector<T2>, vector<T3>, vector<T4>, vector<T5> > readArrays(int size);
template<typename T> vector<vector<T> > readTable(int rows, int cols);
string readLine();
};
inline bool isWhitespace(int c) {
return isspace(c) || c == EOF;
}
int Input::skipWhitespace() {
int c;
do {
c = get();
if (exhausted) {
error = END_OF_FILE;
return c;
}
} while (isWhitespace(c));
return c;
}
Input::Input(std::istream &in) : in(in) {
}
inline int Input::get() {
int result = in.get();
if (result == EOF) {
exhausted = true;
}
return result;
}
template<typename T>
T Input::readType() {
error = INVALID_CALL;
return nullptr;
}
template<typename T>
T Input::readInteger() {
error = OK;
int c = skipWhitespace();
if (error != OK) {
return 0;
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = get();
}
T res = 0;
do {
if (!isdigit(c)) {
error = UNEXPECTED_SYMBOL;
return 0;
}
res *= 10;
res += c - '0';
c = get();
} while (!isWhitespace(c));
return res * sgn;
}
template<>
int Input::readType() {
return readInteger<int>();
}
template<>
ll Input::readType() {
return readInteger<ll>();
}
template<>
char Input::readType() {
error = OK;
int c = skipWhitespace();
if (error != OK) {
return 0;
}
return c;
}
template<>
string Input::readType() {
error = OK;
int c = skipWhitespace();
if (error != OK) {
return "";
}
vector<char> res;
do {
if (error != OK) {
return "";
}
res.push_back(c);
} while (!isWhitespace(c = get()));
return string(res.begin(), res.end());
}
inline int Input::readInt() {
return readType<int>();
}
inline ll Input::readLong() {
return readType<ll>();
}
template<typename T>
vector<T> Input::readArray(int size) {
vector<T> res;
res.reserve(size);
for (int i = 0; i < size; i++) {
res.push_back(readType<T>());
if (error != OK) {
res.clear();
return res;
}
}
return res;
}
vector<int> Input::readIntArray(int size) {
return readArray<int>(size);
}
template<typename T1, typename T2>
tuple<vector<T1>, vector<T2> > Input::readArrays(int size) {
vector<T1> v1;
vector<T2> v2;
v1.reserve(size);
v2.reserve(size);
for (int i = 0; i < size; ++i) {
v1.push_back(readType<T1>());
v2.push_back(readType<T2>());
}
return make_tuple(v1, v2);
}
string Input::readString() {
return readType<string>();
}
template<typename T>
vector<vector<T>> Input::readTable(int rows, int cols) {
vector<vector<T> > result;
result.reserve(rows);
for (int i = 0; i < rows; ++i) {
result.push_back(readArray<T>(cols));
}
return result;
}
string Input::readLine() {
error = OK;
int c = skipWhitespace();
if (error != OK) {
return "";
}
int length = 0;
vector<char> res;
do {
if (error != OK) {
return "";
}
res.push_back(c);
if (!isWhitespace(c)) {
length = res.size();
}
c = get();
} while (c != '\n' && c != '\r' && c != EOF);
return string(res.begin(), res.begin() + length);
}
template<typename T1, typename T2, typename T3>
tuple<vector<T1>, vector<T2>, vector<T3> > Input::readArrays(int size) {
vector<T1> v1;
vector<T2> v2;
vector<T3> v3;
v1.reserve(size);
v2.reserve(size);
v3.reserve(size);
for (int i = 0; i < size; ++i) {
v1.push_back(readType<T1>());
v2.push_back(readType<T2>());
v3.push_back(readType<T3>());
}
return make_tuple(v1, v2, v3);
}
template<typename T1, typename T2, typename T3, typename T4>
tuple<vector<T1>, vector<T2>, vector<T3>, vector<T4> > Input::readArrays(int size) {
vector<T1> v1;
vector<T2> v2;
vector<T3> v3;
vector<T4> v4;
v1.reserve(size);
v2.reserve(size);
v3.reserve(size);
v4.reserve(size);
for (int i = 0; i < size; ++i) {
v1.push_back(readType<T1>());
v2.push_back(readType<T2>());
v3.push_back(readType<T3>());
v4.push_back(readType<T4>());
}
return make_tuple(v1, v2, v3, v4);
}
template<typename T1, typename T2, typename T3, typename T4, typename T5>
tuple<vector<T1>, vector<T2>, vector<T3>, vector<T4>, vector<T5> > Input::readArrays(int size) {
vector<T1> v1;
vector<T2> v2;
vector<T3> v3;
vector<T4> v4;
vector<T5> v5;
v1.reserve(size);
v2.reserve(size);
v3.reserve(size);
v4.reserve(size);
v5.reserve(size);
for (int i = 0; i < size; ++i) {
v1.push_back(readType<T1>());
v2.push_back(readType<T2>());
v3.push_back(readType<T3>());
v4.push_back(readType<T4>());
v5.push_back(readType<T5>());
}
return make_tuple(v1, v2, v3, v4, v5);
}
#endif //JHELPER_EXAMPLE_PROJECT_INPUT_H
//
// Created by egor on 31.10.2019.
//
#ifndef JHELPER_EXAMPLE_PROJECT_OUTPUT_H
#define JHELPER_EXAMPLE_PROJECT_OUTPUT_H
class Output {
private:
ostream& out;
template<typename T> void printSingle(const T& value);
template<typename T> void printSingle(const vector<T>& value);
template<typename T, typename U> void printSingle(const pair<T, U>& value);
public:
Output(ostream& out);
void print();
template<typename T, typename...Targs>void print(const T& first, const Targs... args);
template<typename...Targs>void printLine(const Targs... args);
void flush();
};
Output::Output(ostream &out) : out(out) {
out << setprecision(12);
}
void Output::print() {
}
template<typename T, typename... Targs>
void Output::print(const T& first, const Targs... args) {
printSingle(first);
if (sizeof...(args) != 0) {
out << ' ';
print(args...);
}
}
template<typename T>
void Output::printSingle(const T& value) {
out << value;
}
template<typename... Targs>
void Output::printLine(const Targs... args) {
print(args...);
out << '\n';
}
void Output::flush() {
out.flush();
}
template<typename T>
void Output::printSingle(const vector<T>& array) {
unsigned int size = array.size();
for (int i = 0; i < size; ++i) {
out << array[i];
if (i + 1 != size) {
out << ' ';
}
}
}
template<typename T, typename U>
void Output::printSingle(const pair<T, U>& value) {
out << value.first << ' ' << value.second;
}
#endif //JHELPER_EXAMPLE_PROJECT_OUTPUT_H
//
// Created by egor on 31.10.2019.
//
#ifndef JHELPER_EXAMPLE_PROJECT_DSU_H
#define JHELPER_EXAMPLE_PROJECT_DSU_H
//
// Created by egor on 31.10.2019.
//
#ifndef JHELPER_EXAMPLE_PROJECT_ALGO_H
#define JHELPER_EXAMPLE_PROJECT_ALGO_H
template <typename T>
inline void unique(vector<T>& v) {
v.resize(unique(all(v)) - v.begin());
}
vi createOrder(int n) {
vi order(n);
for (int i = 0; i < n; i++) {
order[i] = i;
}
return order;
}
template <typename T>
inline vector<vector<T> > makeArray(int a, int b) {
return vector<vector<T> >(a, vector<T>(b));
}
//template <typename T>
//inline vector<vector<vector<T> > > makeArray(int a, int b, int c) {
// return vector<vector<vector<T> > >(a, makeArray<T>(b, c));
//}
template <typename T>
inline vector<vector<T> > makeArray(int a, int b, T init) {
return vector<vector<T> >(a, vector<T>(b, init));
}
template <typename T>
inline vector<vector<vector<T> > > makeArray(int a, int b, int c, T init) {
return vector<vector<vector<T> > >(a, makeArray<T>(b, c, init));
}
template <typename T>
inline void addAll(vector<T>& v, const vector<T>& toAdd) {
v.insert(v.end(), toAdd.begin(), toAdd.end());
}
#endif //JHELPER_EXAMPLE_PROJECT_ALGO_H
class DSU {
private:
vi id;
vi size;
int setCount;
public:
DSU(int n);
int get(int i);
int getSize(int i) { return size[get(i)]; }
int getSetCount() { return setCount; }
bool join(int a, int b);
};
DSU::DSU(int n) {
id = createOrder(n);
size = vi(n, 1);
setCount = n;
}
int DSU::get(int i) {
if (id[i] == i) {
return i;
}
return id[i] = get(id[i]);
}
bool DSU::join(int a, int b) {
a = get(a);
b = get(b);
if (a == b) {
return false;
}
size[a] += size[b];
size[b] = 0;
id[b] = a;
setCount--;
return true;
}
#endif //JHELPER_EXAMPLE_PROJECT_DSU_H
//
// Created by egor on 04.11.2019.
//
#ifndef JHELPER_EXAMPLE_PROJECT_GRAPH_H
#define JHELPER_EXAMPLE_PROJECT_GRAPH_H
template <typename W, typename C>
class WeightedFlowEdge {
private:
WeightedFlowEdge<W, C>* reverseEdge;
public:
const int from;
const int to;
W weight;
C capacity;
int id;
WeightedFlowEdge(int from, int to, W weight, C capacity) : from(from), to(to), weight(weight), capacity(capacity) {
reverseEdge = new WeightedFlowEdge(this);
}
WeightedFlowEdge<W, C>* transposed() { return nullptr; }
WeightedFlowEdge<W, C>* reverse() { return reverseEdge; }
void push(C flow) {
capacity -= flow;
reverseEdge->capacity += flow;
}
C flow() const {
return reverseEdge->capacity;
}
private:
WeightedFlowEdge(WeightedFlowEdge<W, C>* reverse) : from(reverse->to), to(reverse->from), weight(-reverse->weight), capacity(0) {
reverseEdge = reverse;
}
};
template <typename C>
class FlowEdge {
private:
FlowEdge<C>* reverseEdge;
public:
const int from;
const int to;
C capacity;
int id;
FlowEdge(int from, int to, C capacity) : from(from), to(to), capacity(capacity) {
reverseEdge = new FlowEdge(this);
}
FlowEdge<C>* transposed() { return nullptr; }
FlowEdge<C>* reverse() { return reverseEdge; }
void push(C flow) {
capacity -= flow;
reverseEdge->capacity += flow;
}
C flow() const {
return reverseEdge->capacity;
}
private:
FlowEdge(FlowEdge<C>* reverse) : from(reverse->to), to(reverse->from), capacity(0) {
reverseEdge = reverse;
}
};
template <typename W>
class WeightedEdge {
public:
const int from;
const int to;
W weight;
int id;
WeightedEdge(int from, int to, W weight) : from(from), to(to), weight(weight) {
}
WeightedEdge<W>* transposed() { return nullptr; }
WeightedEdge<W>* reverse() { return nullptr; }
};
template <typename W>
class BidirectionalWeightedEdge {
private:
BidirectionalWeightedEdge<W>* transposedEdge;
public:
const int from;
const int to;
W weight;
int id;
BidirectionalWeightedEdge(int from, int to, W weight) : from(from), to(to), weight(weight) {
transposedEdge = new BidirectionalWeightedEdge(this);
}
BidirectionalWeightedEdge<W>* transposed() { return transposedEdge; }
BidirectionalWeightedEdge<W>* reverse() { return nullptr; }
private:
BidirectionalWeightedEdge(BidirectionalWeightedEdge<W>* transposed) : from(transposed->to), to(transposed->from), weight(transposed->weight) {
transposedEdge = transposed;
}
};
class SimpleEdge {
public:
const int from;
const int to;
int id;
SimpleEdge(int from, int to) : from(from), to(to) {
}
SimpleEdge* transposed() { return nullptr; }
SimpleEdge* reverse() { return nullptr; }
};
class BidirectionalEdge {
private:
BidirectionalEdge* transposedEdge;
public:
const int from;
const int to;
int id;
BidirectionalEdge(int from, int to) : from(from), to(to) {
transposedEdge = new BidirectionalEdge(this);
}
BidirectionalEdge* transposed() { return transposedEdge; }
BidirectionalEdge* reverse() { return nullptr; }
private:
BidirectionalEdge(BidirectionalEdge* transposed) : from(transposed->to), to(transposed->from) {
transposedEdge = transposed;
}
};
template <class Edge>
class Graph {
public:
int vertexCount;
int edgeCount = 0;
vector<vector<Edge*> > edges;
Graph(int vertexCount) : vertexCount(vertexCount) {
edges.resize(vertexCount);
}
void addEdge(Edge* edge) {
edge->id = edgeCount;
edges[edge->from].push_back(edge);
if (edge->reverse() != nullptr) {
edge->reverse()->id = edgeCount;
edges[edge->reverse()->from].push_back(edge->reverse());
}
if (edge->transposed() != nullptr) {
edges[edge->transposed()->from].push_back(edge->transposed());
edge->transposed()->id = edgeCount;
if (edge->transposed()->reverse() != nullptr) {
edges[edge->transposed()->reverse()->from].push_back(edge->transposed()->reverse());
edge->transposed()->reverse()->id = edgeCount;
}
}
edgeCount++;
}
};
typedef FlowEdge<ll> LongFlowEdge;
typedef WeightedEdge<ll> LongWeightedEdge;
typedef FlowEdge<int> IntFlowEdge;
typedef WeightedEdge<int> IntWeightedEdge;
typedef BidirectionalWeightedEdge<ll> LongBiWeightedEdge;
typedef BidirectionalWeightedEdge<int> IntBiWeightedEdge;
#endif //JHELPER_EXAMPLE_PROJECT_GRAPH_H
#ifndef CPP_LCA_H
#define CPP_LCA_H
//
// Created by kulikov on 11/7/2019.
//
#include <functional>
#ifndef JHELPER_EXAMPLE_PROJECT_INTERVAL_TREE_H
#define JHELPER_EXAMPLE_PROJECT_INTERVAL_TREE_H
template<typename Value, typename Delta, Value defaultValue = 0, Delta defaultDelta = 0>
class IntervalTree {
private:
const int size;
const function<Value(Value, Value)> &joinValue;
const function<Delta(Delta, Delta)> &joinDelta;
const function<Value(Value, Delta, int, int)> &accumulate;
const function<Value(int)> &initValue;
vector<Value> value;
vector<Delta> delta;
void init(int root, int left, int right) {
if (left + 1 == right) {
value[root] = initValue(left);
} else {
int mid = (left + right) >> 1;
init(2 * root + 1, left, mid);
init(2 * root + 2, mid, right);
value[root] = joinValue(value[2 * root + 1], value[2 * root + 2]);
}
}
void apply(int root, Delta dlt, int left, int right) {
value[root] = accumulate(value[root], dlt, left, right);
delta[root] = joinDelta(delta[root], dlt);
}
void pushDown(int root, int left, int mid, int right) {
apply(2 * root + 1, delta[root], left, mid);
apply(2 * root + 2, delta[root], mid, right);
delta[root] = defaultDelta;
}
void update(int root, int left, int right, int from, int to, Delta dlt) {
if (left >= from && right <= to) {
apply(root, dlt, left, right);
return;
}
if (right <= from || left >= to) {
return;
}
int mid = (left + right) >> 1;
pushDown(root, left, mid, right);
update(2 * root + 1, left, mid, from, to, dlt);
update(2 * root + 2, mid, right, from, to, dlt);
}
Value query(int root, int left, int right, int from, int to) {
if (left >= from && right <= to) {
return value[root];
}
if (right <= from || left >= to) {
return defaultValue;
}
int mid = (left + right) >> 1;
pushDown(root, left, mid, right);
return joinValue(query(2 * root + 1, left, mid, from, to), query(2 * root + 2, mid, right, from, to));
}
public:
IntervalTree(int size, const function<Value(Value, Value)> &joinValue,
const function<Delta(Delta, Delta)> &joinDelta,
function<Value(Value, Delta, int, int)> &accumulate,
const function<Value(int)> &initValue = [](int at) -> Value { return defaultValue; }) :
size(size), joinValue(joinValue), joinDelta(joinDelta), accumulate(accumulate), initValue(initValue) {
int vertexSize = size * 4;
value = vector<Value>(vertexSize);
delta = vector<Delta>(vertexSize, defaultDelta);
init(0, 0, size);
}
void update(int from, int to, Delta delta) {
update(0, 0, size, from, to, delta);
}
Value query(int from, int to) {
return query(0, 0, size, from, to);
}
};
template <typename Value, Value defaultValue = 0>
class ReadOnlyIntervalTree {
private:
const int size;
const function<Value(Value, Value)> &joinValue;
vector<Value> value;
void init(int root, int left, int right, const vector<Value>& array) {
if (left + 1 == right) {
value[root] = array[left];
} else {
int mid = (left + right) >> 1;
init(2 * root + 1, left, mid, array);
init(2 * root + 2, mid, right, array);
value[root] = joinValue(value[2 * root + 1], value[2 * root + 2]);
}
}
Value query(int root, int left, int right, int from, int to) {
if (left >= from && right <= to) {
return value[root];
}
if (right <= from || left >= to) {
return defaultValue;
}
int mid = (left + right) >> 1;
return joinValue(query(2 * root + 1, left, mid, from, to), query(2 * root + 2, mid, right, from, to));
}
public:
ReadOnlyIntervalTree(const vector<Value>& array, const function<Value(Value, Value)> &joinValue) :
size(array.size()), joinValue(joinValue) {
int vertexSize = size * 4;
value = vector<Value>(vertexSize);
init(0, 0, size, array);
}
Value query(int from, int to) {
return query(0, 0, size, from, to);
}
};
#endif //JHELPER_EXAMPLE_PROJECT_INTERVAL_TREE_H
template <class Edge>
class LCA {
private:
vi order;
vi position;
Graph<Edge>* graph;
ReadOnlyIntervalTree<int, -1>* lcaTree;
vi level;
public:
LCA(Graph<Edge>* graph, int root = 0) : graph(graph) {
int vertexCount = graph->vertexCount;
order = vi(2 * vertexCount - 1);
position = vi(vertexCount, -1);
level = vi(vertexCount);
vi index = vi(vertexCount);
vi last = vi(vertexCount);
vi stack = vi(vertexCount);
stack[0] = root;
int size = 1;
int j = 0;
last[root] = -1;
while (size > 0) {
int vertex = stack[--size];
if (position[vertex] == -1) {
position[vertex] = j;
}
order[j++] = vertex;
if (last[vertex] != -1) {
level[vertex] = level[last[vertex]] + 1;
}
while (index[vertex] < graph->edges[vertex].size() && last[vertex] == graph->edges[vertex][index[vertex]]->to) {
index[vertex]++;
}
if (index[vertex] < graph->edges[vertex].size()) {
stack[size++] = vertex;
int to = graph->edges[vertex][index[vertex]]->to;
stack[size++] = graph->edges[vertex][index[vertex]]->to;
last[to] = vertex;
index[vertex]++;
}
}
lcaTree = new ReadOnlyIntervalTree<int, -1>(order, [this](int left, int right) -> int {
if (left == -1) {
return right;
}
if (right == -1) {
return left;
}
if (level[left] < level[right]) {
return left;
}
return right;
});
}
int getPosition(int vertex) { return position[vertex]; }
int getLCA(int first, int second) {
return lcaTree->query(min(position[first], position[second]), max(position[first], position[second]) + 1);
}
int getLevel(int vertex) {
return level[vertex];
}
int getPathLength(int first, int second) {
return level[first] + level[second] - 2 * level[getLCA(first, second)];
}
};
#endif //CPP_LCA_H
class c {
int fillDown(int vertex, int last, Graph<BidirectionalEdge>& graph, vi& qty, vi& part, vi& down) {
down[vertex] = qty[part[vertex]];
for (auto edge : graph.edges[vertex]) {
if (edge->to != last) {
down[vertex] += fillDown(edge->to, vertex, graph, qty, part, down);
}
}
return down[vertex];
}
int getOptimal(int vertex, int last, Graph<BidirectionalEdge>& graph, vi& down, int all) {
for (auto edge : graph.edges[vertex]) {
if (edge->to != last && down[edge->to] * 2 > all) {
return getOptimal(edge->to, vertex, graph, down, all);
}
}
return vertex;
}
public:
void solve(istream& inp, ostream& outp) {
Input in(inp);
Output out(outp);
int n = in.readInt();
int m = in.readInt();
int q = in.readInt();
vi u, v, a, b;
tie(u, v) = in.readArrays<int, int>(m);
tie(a, b) = in.readArrays<int, int>(q);
decreaseByOne(u, v, a, b);
DSU dsu(n);
for (int i = 0; i < m; ++i) {
dsu.join(u[i], v[i]);
}
int setCount = dsu.getSetCount();
vi heads;
for (int i = 0; i < n; i++) {
if (dsu.get(i) == i) {
heads.push_back(i);
}
}
vi did(n);
for (int i = 0; i < n; i++) {
did[i] = lower_bound(all(heads), dsu.get(i)) - heads.begin();
}
vector<vi> parts(setCount);
for (int i = 0; i < n; i++) {
parts[did[i]].push_back(i);
}
vi size(setCount);
for (int i = 0; i < n; i++) {
size[did[i]]++;
}
vector<Graph<BidirectionalEdge>*> graphs;
graphs.reserve(setCount);
for (int i = 0; i < setCount; i++) {
graphs.push_back(new Graph<BidirectionalEdge>(size[i]));
}
vi convert(n);
for (int i = 0; i < n; i++) {
int id = did[i];
convert[i] = lower_bound(all(parts[id]), i) - parts[id].begin();
}
for (int i = 0; i < m; i++) {
int id = did[v[i]];
graphs[id]->addEdge(new BidirectionalEdge(convert[v[i]], convert[u[i]]));
}
vector<LCA<BidirectionalEdge>*> lcas;
for (int i = 0; i < setCount; i++) {
lcas.push_back(new LCA<BidirectionalEdge>(graphs[i]));
}
ll answer = 0;
vi qty(n);
for (int i = 0; i < q; ++i) {
if (did[a[i]] != did[b[i]]) {
qty[a[i]]++;
qty[b[i]]++;
} else {
answer += lcas[did[a[i]]]->getPathLength(convert[a[i]], convert[b[i]]);
}
}
for (int i = 0; i < setCount; i++) {
vi down(parts[i].size());
fillDown(0, -1, *graphs[i], qty, parts[i], down);
int optimal = getOptimal(0, -1, *graphs[i], down, down[0]);
for (int j = 0; j < parts[i].size(); j++) {
answer += lcas[i]->getPathLength(j, optimal) * ll(qty[parts[i][j]]);
}
}
out.printLine(answer);
}
};
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
c solver;
std::istream& in(std::cin);
std::ostream& out(std::cout);
solver.solve(in, out);
return 0;
}