#include<bits/stdc++.h>
using namespace std;

int n, m, k;
char a[1001][1001];
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, -1, 0, 1};

void dfs(int i, int j, int &cnt){
    a[i][j] = '.';
    ++cnt;
    for(int id=0; id<4; id++){
        int ni = i + dx[id];
        int nj = j + dy[id];
        if(1 <= ni and ni <= n and 1 <= nj and nj <= m and a[ni][nj] == '#'){
            dfs(ni, nj, cnt);
        }
    }
}

void solve(){
    cin >> n >> m >> k;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            a[i][j] = '.';
        }
    }
    for(int i=1; i<=k; i++){
        int x, y; cin >> x >> y;
        a[x][y] = '#';
    }
    int res = 0;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            if(a[i][j] == '#'){
                int cnt = 0;
                dfs(i, j, cnt);
                res = max(res, cnt);
            }
        }
    }
    cout << res;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

#include<bits/stdc++.h>
using namespace std;

#define el '\n'

int n, ok[101][101], vis[101];
vector<int> a[101];

void dfs(int &u){
    vis[u] = 1;
    for(int &v : a[u]){
        if(!vis[v] and ok[u][v]) dfs(v);
    }
}

int check(int i, int j){
    for(int u=1; u<=n; u++) vis[u] = 0;
    ok[i][j] = 0;
    int res = 0;
    for(int u=1; u<=n; u++){
        if(!vis[u]){
            dfs(u);
            ++res;
        }
    }
    ok[i][j] = 1;
    return res;
}

void solve(){
    cin >> n;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            cin >> ok[i][j];
            if(ok[i][j]) a[i].push_back(j);
        }
    }
    int tplt = 0;
    for(int i=1; i<=n; i++){
        if(!vis[i]){
            dfs(i);
            ++tplt;
        }
    }
    int res = 0;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            if(ok[i][j] and check(i, j) > tplt){
                ++res;
            }
        }
    }
    cout << res;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

#include<bits/stdc++.h>
using namespace std;

#define el '\n'
#define mxn 100005

int n, m, d[mxn], sz[mxn];
 
int get(int u){
    if(u == d[u]) return u;
    return d[u] = get(d[u]);
}
 
void uni(int x, int y){
    x = get(x); y = get(y);
    if(x == y) return;
    if(x > y) swap(x, y);
    d[y] = x;
    sz[x] += sz[y];
}
 
void solve(){
    cin >> n >> m;
    for(int i=1; i<=n; i++){
        d[i] = i;
        sz[i] = 1;
    }
    while(m--){
        int x, y; cin >> x >> y;
        uni(x, y);
    }
    int mx = 0;
    for(int i=2; i<=n; i++){
        int x = get(i);
        if(x > 1){
            mx = max(mx, sz[x]);
        }
    }
    cout << sz[1] + mx;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

#include<bits/stdc++.h>
using namespace std;

#define el '\n'
#define mxn 

int n, m, s, t;
vector<int> a[105];
bool vis[105];
 
void dfs(int u){
    vis[u] = 1;
    for(int &v : a[u]){
        if(!vis[v]) dfs(v);
    }
}
 
void solve(){
    cin >> n >> m >> s >> t;
    while(m--){
        int x, y; cin >> x >> y;
        a[x].push_back(y);
    }
    int res = 0;
    for(int i=1; i<=n; i++){
        memset(vis, 0, sizeof vis);
        vis[i] = 1;
        dfs(s);
        if(!vis[t]) ++res;
    }
    cout << res << el;
    for(int i=1; i<=n; i++) a[i].clear();
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; cin >> tc;
    while(tc--) solve();
}

#include<bits/stdc++.h>
using namespace std;

#define el cout << '\n'

int n, m, vis[1001];
vector<int> ke[1001];
stack<int> st;

void dfs(int u, int x){
    vis[u] = 1;
    for(int &v : ke[u]) if(!vis[v]) dfs(v, x);
    if(x == 0) st.push(u);
}

void Longg(){
    cin >> n >> m;
    while(m--){
        int u, v; cin >> u >> v;
        ke[u].push_back(v);
    }
    for(int i=1; i<=n; i++) if(!vis[i]){
        dfs(i, 0);
    }
    for(int i=1; i<=n; i++) vis[i] = 0;
    int res = 0;
    while(!st.empty()){
        int u = st.top(); st.pop();
        if(vis[u]) continue;
        dfs(u, 1);
        ++res;
    }
    cout << res;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int o = 1; //cin >> o;
    while(o--) solve();
}

#include<bits/stdc++.h>
using namespace std;

#define el '\n'
#define mxn 100005

int n, m, a[mxn], p[mxn], c[mxn];

int get(int u){
    if(u == p[u]) return u;
    return p[u] = get(p[u]);
}

void solve(){
    cin >> n >> m;
    for(int i=1; i<=n; i++){
        cin >> a[i];
        p[i] = i;
        c[i] = a[i];
    }
    while(m--){
        int x, y; cin >> x >> y;
        x = get(x); y = get(y);
        if(c[x] < c[y]) p[y] = x;
        else p[x] = y;
    }
    long long res = 0;
    for(int i=1; i<=n; i++){
        int u = get(i);
        res += c[u];
        c[u] = 0;
    }
    cout << res;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

#include<bits/stdc++.h>
using namespace std;

const int mxn = 1e5 + 7;

int n, k, m; // các biến đề cho
int f[mxn]; // f[i]: thời gian tối thiểu người thứ i đến được lối thoát
vector<int> a[mxn]; // danh sách kề
bool ex[mxn]; // ex[i] = 1 -> lối thoát, ex[i] = 0 -> phòng bình thường

void bfs(int s){
    queue<int> q;
    q.push(s);
    while(!q.empty()){
        int u = q.front(); q.pop();
        for(int &v : a[u]){
            // phòng v không phải lối thoát và
            // cách đi này tốn ít thời gian hơn các cách trước
            if(!ex[v] and f[u] + 1 < f[v]){
                f[v] = f[u] + 1;
                q.push(v);
            }
        }
    }
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    cin >> n >> k;
    // ban đầu gán giá trị lớn cho thời gian
    for(int i=1; i<=n; i++) f[i] = 1e8;
    while(k--){
        int room; cin >> room;
        ex[room] = 1; // room là lối thoát
        f[room] = 0; // không tốn thời gian di chuyển
    }
    cin >> m;
    while(m--){
        // thiết kế danh sách kề
        int x, y; cin >> x >> y;
        a[x].push_back(y);
        a[y].push_back(x);
    }
    // BFS đa luồng -> xuất phát từ các lối thoát
    // đi đến các phòng khác để tìm thời gian tối thiểu
    for(int i=1; i<=n; i++) if(ex[i]) bfs(i);
    // in ra kết quả
    for(int i=1; i<=n; i++) cout << f[i] << ' ';
}

#include<bits/stdc++.h>
using namespace std;

#define el '\n'
#define mxn 10004

int p[mxn];
int get(int u){
    if(u == p[u]) return u;
    return p[u] = get(p[u]);
}

void solve(){
    int n, q; cin >> n >> q;
    for(int i=1; i<=n; i++) p[i] = i;
    while(q--){
        int x, y, z; cin >> x >> y >> z;
        if(z == 1){
            x = get(x); y = get(y);
            if(x > y) swap(x, y);
            p[y] = x;
        }else{
            cout << (get(x) == get(y) ? "Yes\n" : "No\n");
        }
    }
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}  

#include<bits/stdc++.h>
using namespace std;

#define el '\n'
#define mxn 100005

int n, q, a[mxn], p[mxn];
map<int, int> f[mxn];

int get(int u){
    if(u == p[u]) return u;
    return p[u] = get(p[u]);
}

void solve(){
    cin >> n >> q;
    for(int i=1; i<=n; i++){
        cin >> a[i];
        p[i] = i;
        ++f[i][a[i]];
    }
    while(q--){
        int t, x, y; cin >> t >> x >> y;
        if(t == 1){
            x = get(x); y = get(y);
            if(x == y) continue;
            if(x > y) swap(x, y);
            p[y] = x;
            for(auto &[i, j] : f[y]){
                f[x][i] += j;
            }
        }else{
            x = get(x);
            cout << f[x][y] << el;
        }
    }
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

#include<bits/stdc++.h>
using namespace std;

#define pe pair<int, int>
int n, m, k, p[2][200005];
map<pe, int> mp;

int get(int u, int p[]){
    if(u == p[u]) return u;
    return p[u] = get(p[u], p);
}

void solve(){
    cin >> n >> m >> k;
    for(int i=1; i<=n; i++){
        p[0][i] = p[1][i] = i;
    }
    for(int i=0; i<m; i++){
        int x, y; cin >> x >> y;
        x = get(x, p[0]); 
        y = get(y, p[0]);
        if(x > y) swap(x, y);
        p[0][y] = x;
    }
    for(int i=0; i<k; i++){
        int x, y; cin >> x >> y;
        x = get(x, p[1]);
        y = get(y, p[1]);
        if(x > y) swap(x, y);
        p[1][y] = x;
    }
    for(int i=1; i<=n; i++){
        ++mp[{get(i, p[0]), get(i, p[1])}];
    }
    for(int i=1; i<=n; i++){
        cout << mp[{p[0][i], p[1][i]}] << ' ';
    }
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

#include<bits/stdc++.h>
using namespace std;

#define pe pair<ld, ld>
#define fi first
#define se second
#define el '\n'
#define ld long double

struct canh{
    int u, v;
    ld w;
};
 
int n, m, p[1005];
vector<canh> v;
 
int get(int u){
    if(u == p[u]) return u;
    return p[u] = get(p[u]);
}
 
ld dis(pe a, pe b){
    return sqrtl((a.fi - b.fi) * (a.fi - b.fi) + (a.se - b.se) * (a.se - b.se));
}
 
bool cmp(canh a, canh b){
    return a.w < b.w;
}
 
void solve(){
    cin >> n >> m;
    pe a[n+5];
    for(int i=1; i<=n; i++){
        p[i] = i;
    }
    for(int i=1; i<=n; i++){
        cin >> a[i].fi >> a[i].se;
    }
    for(int i=1; i<=m; i++){
        int x, y; cin >> x >> y;
        x = get(x); y = get(y);
        if(x == y) continue;
        p[y] = x;
    }
    for(int i=1; i<n; i++){
        for(int j=i+1; j<=n; j++){
            v.push_back({i, j, dis(a[i], a[j])});
        }
    }
    sort(v.begin(), v.end(), cmp);
    ld mst = 0;
    int sz = 0;
    for(int i=0; i<v.size() and sz < n - 1; i++){
        canh c = v[i];
        int x = get(c.u), y = get(c.v);
        if(x == y) continue;
        p[y] = x;
        mst += c.w;
        ++sz;
    }
    cout << fixed << setprecision(2) << mst;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

#include<bits/stdc++.h>
using namespace std;

#define pe pair<int, int>
#define fi first
#define se second
#define el '\n'
#define mxn 100005
#define int long long

int n, m, s, t, dp[mxn];
vector<pe> a[mxn];

void dijkstra(){
    for(int i=1; i<=n; i++) dp[i] = 1e16;
    dp[s] = 0;
    priority_queue<pe, vector<pe>, greater<pe>> q;
    q.push({dp[s], s});
    while(!q.empty()){
        auto top = q.top(); q.pop();
        int u = top.se;
        int kc = top.fi;
        if(kc > dp[u]) continue;
        for(auto &i : a[u]){
            int v = i.fi;
            int w = i.se;
            if(dp[u] + w < dp[v]){
                dp[v] = dp[u] + w;
                q.push({dp[v], v});
            }
        }
    }
    cout << dp[t];
}

void solve(){
    cin >> n >> m >> s >> t;
    while(m--){
        int x, y, w; cin >> x >> y >> w;
        a[x].push_back({y, w});
        a[y].push_back({x, w});
    }
    dijkstra();
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

#include<bits/stdc++.h>
using namespace std;

#define el '\n'
#define mxn 303

int n, m, q, d[mxn][mxn];
 
void solve(){
    cin >> n >> m >> q;
    for(int i=1; i<n; i++){
        for(int j=i+1; j<=n; j++){
            d[i][j] = d[j][i] = 1e9;
        }
    }
    while(m--){
        int x, y, w; cin >> x >> y >> w;
        d[x][y] = w;
    }
    for(int k=1; k<=n; k++){
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                d[i][j] = min(d[i][j], max(d[i][k], d[k][j]));
            }
        }
    }
    while(q--){
        int x, y; cin >> x >> y;
        if(d[x][y] != 1e9) cout << d[x][y] << el;
        else cout << "-1\n";
    }
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

// LonggVuz
#include<bits/stdc++.h>
using namespace std;
#define el cout << '\n'
#define inc(i, a, b, c) for(int32_t i=a; i<=b; i+=c)
#define dec(i, a, b, c) for(int32_t i=a; i>=b; i-=c)
#define fo(i, a, b) for(int32_t i=a; i<=b; i++)
#define fd(i, a, b) for(int32_t i=a; i>=b; i--)
#define out(x) return void(cout << (x));
#define all(x) begin(x), end(x)
#define len(x) (int)(x).size()
#define vec vector
#define pub push_back
#define pob pop_back
#define int int64_t

const int mod = 1e9 + 7;
const int oo = 1e18 + 7;
const int mxn = 1e3 + 7;

#define pe pair<int, int>
#define fi first
#define se second
int n, m, a[mxn][mxn], dp[mxn][mxn];

void LonggVuz(){
    cin >> n >> m;
    fo(i, 1, n) fo(j, 1, m){
        cin >> a[i][j];
        dp[i][j] = oo;
    }
    queue<pe> q;
    q.push({1, 1});
    dp[1][1] = 0;
    while(!q.empty()){
        auto [i, j] = q.front(); q.pop();
        if(i == n and j == m) break;
        if(i + 1 <= n){
            int c = abs(a[i][j] - a[i + 1][j]);
            if(i + c <= n and dp[i][j] + 1 < dp[i + c][j]){
                dp[i + c][j] = dp[i][j] + 1;
                q.push({i + c, j});
            }
        }
        if(j + 1 <= m){
            int c = abs(a[i][j] - a[i][j + 1]);
            if(j + c <= m and dp[i][j] + 1 < dp[i][j + c]){
                dp[i][j + c] = dp[i][j] + 1;
                q.push({i, j + c});
            }
        }
        if(i + 1 <= n and j + 1 <= m){
            int c = abs(a[i][j] - a[i + 1][j + 1]);
            if(i + c <= n and j + c <= m and dp[i][j] + 1 < dp[i + c][j + c]){
                dp[i + c][j + c] = dp[i][j] + 1;
                q.push({i + c, j + c});
            }
        }
    }
    cout << (dp[n][m] < oo ? dp[n][m] : -1);
}

signed main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    
    signed orz = 1; cin >> orz;
    while(orz --> 0){
        LonggVuz();
        if(orz) el;
    }
    
    cerr << "Execution Time: " << 0.001 * clock() << "s\n";
}

#include<bits/stdc++.h>
using namespace std;

#define el '\n'
#define mxn 100005

int n, sz[mxn];
vector<int> a[mxn];

void dfs(int u, int p = 0){
    sz[u] = 1;
    for(int &v : a[u]){
        if(v != p){
            dfs(v, u);
            sz[u] += sz[v];
        }
    }
}

void solve(){
    cin >> n;
    for(int i=1; i<n; i++){
        int x, y; cin >> x >> y;
        a[x].push_back(y);
        a[y].push_back(x);
    }
    dfs(1);
    for(int i=1; i<=n; i++) cout << sz[i] << ' ';
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

#include<bits/stdc++.h>
using namespace std;

#define el '\n'
#define mxn 100005

int n, d[mxn];
vector<int> a[mxn];

void dfs(int u, int p = 0){
    for(int &v : a[u]){
        if(v != p){
            d[v] = d[u] + 1;
            dfs(v, u);
        }
    }
}

void solve(){
    int k;
    cin >> n >> k;
    for(int i=1; i<n; i++){
        int x, y; cin >> x >> y;
        a[x].push_back(y);
        a[y].push_back(x);
    }
    dfs(1);
    sort(d+1, d+n+1, greater<int>());
    long long res = 0;
    for(int i=1; i<=k; i++) res += d[i];
    cout << res;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

#include<bits/stdc++.h>
using namespace std;

#define el '\n'
#define mxn 100005

int n, res, dp[mxn];
vector<int> a[mxn];
string s;

void dfs(int u, int p = 0){
    if(s[u] == 'W') ++dp[u];
    else --dp[u];
    for(int &v : a[u]){
        if(v != p){
            dfs(v, u);
            dp[u] += dp[v];
        }
    }
    if(dp[u] == 0) ++res;
}

void solve(){
    cin >> n;
    for(int i=2; i<=n; i++){
        int p; cin >> p;
        a[p].push_back(i);
        a[i].push_back(p);
    }
    cin >> s; s = " " + s;
    res = 0;
    dfs(1);
    cout << res << el;
    for(int i=1; i<=n; i++){
        dp[i] = 0;
        a[i].clear();
    }
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; cin >> tc;
    while(tc--) solve();
}

// LonggVuz
#include<bits/stdc++.h>
using namespace std;
#define el cout << '\n'
#define inc(i, a, b, c) for(int32_t i=a; i<=b; i+=c)
#define dec(i, a, b, c) for(int32_t i=a; i>=b; i-=c)
#define fo(i, a, b) for(int32_t i=a; i<=b; i++)
#define fd(i, a, b) for(int32_t i=a; i>=b; i--)
#define out(x) return void(cout << (x));
#define all(x) begin(x), end(x)
#define len(x) (int)(x).size()
#define vec vector
#define pb push_back
#define po pop_back
#define int int64_t

const int mod = 1e9 + 7;
const int oo = 1e18 + 8;
const int mxn = 1e6 + 9;

struct dsu{
    int n; vec<int> p, sz;
    dsu(int _n){
        n = _n; p.resize(n + 5); sz.resize(n + 5);
        fo(i, 1, n) p[i] = i, sz[i] = 1;
    }
    int get(int u){
        if(u == p[u]) return u;
        return p[u] = get(p[u]);
    }
    void uni(int u, int v){
        u = get(u); v = get(v);
        if(u == v) return;
        if(u > v) swap(u, v);
        p[v] = u;
        sz[u] += sz[v];
    }
};

void LonggVuz(){
    int n, m; cin >> n >> m;
    dsu d(n);
    fo(i, 1, m){
        int x, y; cin >> x >> y;
        if(d.get(x) == d.get(y)) continue;
        d.uni(x, y);
    }
    int res = 0;
    fo(i, 1, n) res = max(res, d.sz[d.get(i)]);
    cout << res;
}

signed main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    
    signed orz = 1; //cin >> orz;
    while(orz--){
        LonggVuz();
        if(orz) el;
    }
    
    cerr << "Execution Time: " << 0.001 * clock() << "s\n";
}

// LonggVuz
#include<bits/stdc++.h>
using namespace std;
#define el cout << '\n'
#define inc(i, a, b, c) for(int32_t i=a; i<=b; i+=c)
#define dec(i, a, b, c) for(int32_t i=a; i>=b; i-=c)
#define fo(i, a, b) for(int32_t i=a; i<=b; i++)
#define fd(i, a, b) for(int32_t i=a; i>=b; i--)
#define out(x) return void(cout << (x));
#define all(x) begin(x), end(x)
#define len(x) (int)(x).size()
#define vec vector
#define pub push_back
#define pob pop_back
#define int int64_t

const int mod = 1e9 + 7;
const int oo = 1e18 + 7;
const int mxn = 1e5 + 7;

#define ii pair<int, int>
#define ip pair<int, ii>
#define pi pair<ii, int>
#define pp pair<ii, ii>
#define fi first
#define se second
int n, m, st, en, dp[mxn];
vec<ip> ke[mxn];

void LonggVuz(){
    cin >> n >> m >> st >> en;
    fo(i, 1, m){
        int x, y, t, k; cin >> x >> y >> t >> k;
        ke[x].pub({y, {t, k}});
        ke[y].pub({x, {t, k}});
    }
    fo(i, 1, n) dp[i] = oo;
    dp[st] = 0;
    priority_queue<ip, vec<ip>, greater<ip>> q;
    q.push({0, {0, st}});
    while(!q.empty()){
        auto [cur, tmp] = q.top(); q.pop();
        auto [tg, u] = tmp;
        if(cur > dp[u]) continue;
        for(auto &[v, p] : ke[u]){
            auto [t, k] = p;
            int gan = (tg / k + (tg % k > 0)) * k;
            int d = gan - tg + t;
            if(dp[u] + d < dp[v]){
                dp[v] = dp[u] + d;
                q.push({dp[v], {gan + t, v}});
            }
        }
    }
    // fo(i, 1, n) cout << dp[i], el;
    cout << (dp[en] < oo ? dp[en] : -1);
}

signed main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    
    signed orz = 1; //cin >> orz;
    while(orz --> 0){
        LonggVuz();
        if(orz) el;
    }
    
    cerr << "Execution Time: " << 0.001 * clock() << "s\n";
}

// LonggVuz
#include<bits/stdc++.h>
using namespace std;
#define el cout << '\n'
#define inc(i, a, b, c) for(int32_t i=a; i<=b; i+=c)
#define dec(i, a, b, c) for(int32_t i=a; i>=b; i-=c)
#define fo(i, a, b) for(int32_t i=a; i<=b; i++)
#define fd(i, a, b) for(int32_t i=a; i>=b; i--)
#define out(x) return void(cout << (x));
#define all(x) begin(x), end(x)
#define len(x) (int)(x).size()
#define vec vector
#define pub push_back
#define pob pop_back
#define int int64_t

const int mod = 1e9 + 7;
const int oo = 1e18 + 7;
const int mxn = 2e5 + 7;

struct canh{
    int u, v, w;
};

struct dsu{
    vec<int> p, s; // parent, size
    dsu(int n){
        p.resize(n + 5); iota(all(p), 0); s.resize(n + 5, 1);
    }
    int get(int u){
        return (u == p[u]) ? (u) : (p[u] = get(p[u]));
    }
    bool uni(int u, int v){
        u = get(u); v = get(v);
        if(u == v) return 0;
        if(u > v) swap(u, v);
        p[v] = u; s[u] += s[v];
        return 1;
    }
    int sz(int u){ return s[get(u)]; }
    bool same(int u, int v){ return get(u) == get(v); }
};

int n, m;
vec<canh> ve;

void LonggVuz(){
    cin >> n >> m;
    int res = 0;
    fo(i, 1, m){
        int u, v, w; cin >> u >> v >> w;
        ve.pub({u, v, w});
        res += w;
    }
    sort(all(ve), [&](canh x, canh y){
        return x.w < y.w;
    });
    int cnt = 0;
    dsu d(n);
    for(auto &[u, v, w] : ve){
        if(w >= 0 and cnt >= n - 1) break;
        if(w < 0) res -= w;
        if(d.uni(u, v)){
            ++cnt;
            if(w >= 0) res -= w;
        }
    }
    cout << res;
}

signed main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    
    signed orz = 1; //cin >> orz;
    while(orz --> 0){
        LonggVuz();
        if(orz) el;
    }
    
    cerr << "Execution Time: " << 0.001 * clock() << "s\n";
}

// LonggVuz
#include <bits/stdc++.h>
using namespace std;

#ifdef LonggVuz
#include <LonggVuz.h>
#else
#define debug(...)
#endif

#define el cout << '\n'
#define inc(i, a, b, c) for(int32_t i=a; i<=b; i+=c)
#define dec(i, a, b, c) for(int32_t i=a; i>=b; i-=c)
#define fo(i, a, b) for(int32_t i=a; i<=b; i++)
#define fd(i, a, b) for(int32_t i=a; i>=b; i--)
#define out(x) return void(cout << (x))
#define all(x) begin(x), end(x)
#define len(x) (int)(x).size()
#define vec vector
#define pub push_back
#define pob pop_back
#define dub double
#define int int64_t

const int mod = 1e9 + 7;
const int oo = 1e18 + 7;
const int mxn = 2e5 + 7;

#define pii pair<int, int>
#define fi first
#define se second

int n, m, vt, s, t, dp[mxn];
vec<pii> ke[mxn];

inline void LonggVuz(){
    cin >> n >> m >> vt;
    fo(i, 1, m){
        int x, y, w; cin >> x >> y >> w;
        ke[x].pub({y, w});
        ke[y].pub({x, w});
    }
    cin >> s >> t;
    fo(i, 1, n) dp[i] = oo;
    dp[s] = 0;
    priority_queue<pii, vec<pii>, greater<pii>> q;
    q.push({dp[s], s});
    while(!q.empty()){
        auto [cur, u] = q.top(); q.pop();
        if(cur > dp[u]) continue;
        if(u == t) break;
        int p = 0;
        if(u != s) p = max(p, len(ke[u]) - 2);
        for(auto &[v, w] : ke[u]){
            int c = p * vt + w;
            if(dp[u] + c < dp[v]){
                debug(u, v);
                dp[v] = dp[u] + c;
                q.push({dp[v], v});
            }
        }
    }
    dub res = (dub)1.0 * dp[t] / vt;
    cout << fixed << setprecision(6) << res;
    fo(i, 1, n) ke[i].clear();
}

signed main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    
    signed orz = 1; if(1) cin >> orz;
    while(orz --> 0){
        LonggVuz();
        if(orz) el;
    }
    
    cerr << "Execution Time: " << clock() << "ms\n";
}