#include <iostream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <iterator>
#include <functional>
#include <complex>
#include <queue>
#include <stack>
#include <cmath>
#include <cassert>
#include <tuple>
using namespace std;
typedef long long LL;
typedef complex<double> CMP;
const int INF = 0x1fffffff;
class CandleTimer { public:
int differentTime(vector <int> A, vector <int> B, vector <int> len)
{
if(A.size() == 1) {
// Special case, just in case. All nodes are leaves.
// Either light only one end or both ends.
return 2;
}
// x2, to make all the possible final points on integer coordinates.
for(auto& li: len)
li *= 2;
// Prepare....
const int E = A.size(), V = E+1;
vector<int> leaf;
vector<bool> is_leaf(V, false);
{
vector<int> degree(V);
for(auto a: A) degree[a]++;
for(auto b: B) degree[b]++;
for(int v=0; v<V; ++v)
if(degree[v]==1) {
leaf.push_back(v);
is_leaf[v] = true;
}
}
vector<vector<int>> dist(V, vector<int>(V, INF));
{
for(int i=0; i<V; ++i)
dist[i][i] = 0;
for(int i=0; i<E; ++i)
dist[A[i]][B[i]] = dist[B[i]][A[i]] = len[i];
for(int k=0; k<V; ++k)
for(int i=0; i<V; ++i)
for(int j=0; j<V; ++j)
dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j]);
}
vector<vector<pair<int,int>>> G(V); // len, dest
for(int e=0; e<E; ++e) {
G[A[e]].emplace_back(len[e], B[e]);
G[B[e]].emplace_back(len[e], A[e]);
}
// Compute all possible final points.
enum {EID, POS};
vector<tuple<int,int>> cand;
{
vector<bool> done(V, false);
// Add all leaves as the possible final point
for(int e=0; e<E; ++e) {
if(is_leaf[A[e]] && !done[A[e]])
cand.emplace_back(e, 0), done[A[e]]=true;
if(is_leaf[B[e]] && !done[B[e]])
cand.emplace_back(e, len[e]), done[B[e]]=true;
}
// Add all mid points.
for(int la: leaf)
for(int lb: leaf)
for(int e=0; e<E; ++e)
{
int a=A[e], b=B[e], ll=len[e];
if(dist[la][a]+ll+dist[lb][b] == dist[la][lb]) {
if(abs(dist[la][a] - dist[lb][b]) <= ll) {
tuple<int,int> c(e, (ll+dist[lb][b]-dist[la][a])/2);
// TODO: reduce by done[]
cand.push_back(c);
}
} else if(dist[la][b]+ll+dist[lb][a] == dist[la][lb]) {
if(abs(dist[la][b] - dist[lb][a]) <= ll) {
tuple<int,int> c(e, (ll+dist[la][b]-dist[lb][a])/2);
// TODO: reduce by done[]
cand.push_back(c);
}
}
}
}
// Distance between a candidate point and a node.
function<int(tuple<int,int>,int)> calc_d = [&](tuple<int,int> c, int v) {
return min(
dist[A[get<EID>(c)]][v] + get<POS>(c),
dist[B[get<EID>(c)]][v] + len[get<EID>(c)] - get<POS>(c)
);
};
// Simulate all.
set<int> answer;
for(auto c: cand)
{
vector<pair<int,int>> dist_leaf;
for(int v: leaf)
dist_leaf.emplace_back(calc_d(c, v), v);
sort(dist_leaf.begin(), dist_leaf.end());
for(int i=0; i<dist_leaf.size(); ++i)
{
const int cand_time = dist_leaf[i].first;
if(i>0 && cand_time == dist_leaf[i-1].first)
continue;
// Light all leaves further or equal to dist_leaf[i].
// Can the point |c| be the last point (burning at |cand_time|?)
// Dijkstra.
vector<int> burn_time(V, INF);
{
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> Q;
for(int k=i; k<dist_leaf.size(); ++k)
Q.emplace(0, dist_leaf[k].second);
while(!Q.empty()) {
int d = Q.top().first;
int v = Q.top().second;
Q.pop();
if(burn_time[v] != INF)
continue;
burn_time[v] = d;
for(int i=0; i<G[v].size(); ++i)
{
int dd = G[v][i].first;
int u = G[v][i].second;
if(burn_time[u] == INF)
Q.emplace(d+dd, u);
}
}
}
int bt_min = INF;
for(int e=0; e<E; ++e)
{
int a=A[e], b=B[e], ll=len[e], bt;
if(burn_time[a]+ll == burn_time[b] || burn_time[b]+ll == burn_time[a]) {
bt = max(burn_time[a], burn_time[b]);
} else {
bt = max(burn_time[a], burn_time[b]) + (ll - abs(burn_time[b] - burn_time[a]))/2;
}
bt_min = min(bt_min, bt);
}
if(bt_min >= cand_time)
answer.insert(cand_time);
}
}
return answer.size();
}
};
// BEGIN CUT HERE
#include <ctime>
double start_time; string timer()
{ ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
{ os << "{ ";
for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
void verify_case(const int& Expected, const int& Received) {
bool ok = (Expected == Received);
if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl;
cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
#define END verify_case(_, CandleTimer().differentTime(A, B, len));}
int main(){
CASE(0)
int A_[] = {0,1};
vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_));
int B_[] = {1,2};
vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_));
int len_[] = {10,1};
vector <int> len(len_, len_+sizeof(len_)/sizeof(*len_));
int _ = 2;
END
CASE(1)
int A_[] = {0,0,0};
vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_));
int B_[] = {1,2,3};
vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_));
int len_[] = {1,1,1};
vector <int> len(len_, len_+sizeof(len_)/sizeof(*len_));
int _ = 2;
END
CASE(2)
int A_[] = {0,0,0};
vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_));
int B_[] = {1,2,3};
vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_));
int len_[] = {1,2,3};
vector <int> len(len_, len_+sizeof(len_)/sizeof(*len_));
int _ = 4;
END
CASE(3)
int A_[] = {0,1,1,2,3,3,2,4};
vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_));
int B_[] = {1,2,3,4,5,6,7,8};
vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_));
int len_[] = {5,3,2,4,6,8,7,1};
vector <int> len(len_, len_+sizeof(len_)/sizeof(*len_));
int _ = 7;
END
CASE(4)
int A_[] = {0,0,0,0};
vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_));
int B_[] = {1,2,3,4};
vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_));
int len_[] = {123,456,789,1000};
vector <int> len(len_, len_+sizeof(len_)/sizeof(*len_));
int _ = 8;
END
CASE(5)
int A_[] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30};
vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_));
int B_[] = {0,1,2,0,0,0,1,0,0,0,2,5,4,7,13,13,6,15,11,18,19,21,22,16,19,19,20,18,22,27};
vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_));
int len_[] = {59,58,147,169,34,14,150,55,156,151,130,109,124,15,100,1,156,16,38,97,99,132,150,18,27,91,110,127,15,105};
vector <int> len(len_, len_+sizeof(len_)/sizeof(*len_));
int _ = 65;
END
CASE(6)
int A_[] = {0};
vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_));
int B_[] = {1};
vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_));
int len_[] = {1000};
vector <int> len(len_, len_+sizeof(len_)/sizeof(*len_));
int _ = 2;
END
/*
CASE(7)
int A_[] = ;
vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_));
int B_[] = ;
vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_));
int len_[] = ;
vector <int> len(len_, len_+sizeof(len_)/sizeof(*len_));
int _ = ;
END
CASE(8)
int A_[] = ;
vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_));
int B_[] = ;
vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_));
int len_[] = ;
vector <int> len(len_, len_+sizeof(len_)/sizeof(*len_));
int _ = ;
END
*/
}
// END CUT HERE