wa on #3#9

#include<bits/stdc++.h>
using namespace std;
const int N=1145141;
int n,m,r[N],fa[N][17],dep[N],st[N];
vector<int>s[N],f[N],so[N];
queue<int>q;
int lca(int x,int y)
{
	if(x==y)
	{
		return x;
	}
	if(dep[x]>dep[y])
	{
		swap(x,y);
	}
	for(int i=16;i>=0;i--)
	{
		if(dep[fa[y][i]]>=dep[x])
		{
			y=fa[y][i];
		}
	}
	if(x==y)
	{
		return x;
	}
	for(int i=16;i>=0;i--)
	{
		if(fa[x][i]!=fa[y][i])
		{
			x=fa[x][i];
			y=fa[y][i];
		}
	}
	return fa[x][0];
}
void dfs(int x)
{
	for(int i=0;i<so[x].size();i++)
	{
		dfs(so[x][i]);
		st[x]+=st[so[x][i]];
	}
	st[x]++;
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		int x;
		cin>>x;
		while(x)
		{
			f[i].push_back(x);
			r[i]++;
			s[x].push_back(i);
			cin>>x;
		}
		if(r[i]==0)
		{
			f[0].push_back(0);
			q.push(i);
		}
	}
	while(!q.empty())
	{
		int x=q.front();
		q.pop();
		for(int i=0;i<s[x].size();i++)
		{
			r[s[x][i]]--;
			if(r[s[x][i]]==0)
			{
				q.push(s[x][i]);
			}
		}
		if(f[x].size())
		{
			int l=f[x][0];
			for(int i=1;i<f[x].size();i++)
			{
				l=lca(l,f[x][i]);
			}
			fa[x][0]=l;
			so[l].push_back(x);
			dep[x]=dep[l]+1;
			for(int i=1;i<=16;i++)
			{
				fa[x][i]=fa[fa[x][i-1]][i-1];
			}
		}
	}
	for(int i=1;i<=n;i++)
	{
		if(fa[i][0]==0)
		{
			dfs(i);
		}
	}
	for(int i=1;i<=n;i++)
	{
		cout<<st[i]-1<<"\n";
	}
	return 0;
}