#include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long int ll; typedef pair P; #define all(x) x.begin(),x.end() const ll mod = 1e9+7; const ll INF = 1e9; const ll MAXN = 1e9; struct union_find{ vector par,r,size; union_find(int n) : par(n),r(n),size(n){init(n);} void init(int n){ for(int i = 0; i < n; i++) par[i] = i; for(int i = 0; i < n; i++) r[i] = 0; for(int i = 0; i < n; i++) size[i] = 1; } int find(int x){ if(par[x] == x) return x; else return find(par[x]); } void unite(int x,int y){ x = find(x); y = find(y); if(x == y) return; if(r[x] < r[y]){ par[x] = y; size[y] += size[x]; }else{ par[y] = x; size[x] += size[y]; if(r[x] == r[y]) r[x]++; } } bool same(int x,int y){ return find(x) == find(y); } }; vector > g; vector dist; void dfs(int x,int len){ dist[x] = len; for(int i = 0; i < g[x].size(); i++){ if(dist[g[x][i]]<0) dfs(g[x][i],len+1); } } int main() { int n,m; cin>>n>>m; g.resize(n); dist.resize(n); union_find uf(n); for(int i = 0; i < m; i++){ int a,b; cin>>a>>b; a--;b--; g[a].push_back(b); g[b].push_back(a); uf.unite(a,b); } int q; cin>>q; for(int i = 0; i < q; i++){ int a; cin>>a; a--; dist.assign(dist.size(),-1); dfs(a,0); int max_dist = 0; for(int j = 0; j < n; j++){ max_dist = max(max_dist,dist[j]); } int cnt=0; if(max_dist>1){ while(max_dist-cnt>0){ cnt++; max_dist -= cnt; } } cout << uf.size[uf.find(a)]-1 << " " << cnt <