#include<bits/stdc++.h> using namespace std; long long dp[100005][5]; int vis[100005]; struct node { int x; int y; int z; }; vector<node>q[100005]; void spfa(int x) { queue<int>nh; nh.push(x); vis[x]=1; while(!nh.empty()) { int now=nh.front()...