#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;

const int N = 1e4 + 10 , M = 1e5 + 10;//N为点数，M为边数

int n,m;//n个点，m条边
int h[N],e[M],ne[M],idx;//存图
int dfn[N],low[N],ts;//时间戳dfn[x]表示x点第一次被访问的顺序，追溯值low[x]表示从x点出发，能够访问到的最早时间戳
int stk[N],in_stk[N],top;//stk[]数组模拟栈，in_stk[]标志某点是否在栈中
int scc[N],sizes[N],cnt;//

void add(int a,int b)
{
    e[idx] = b , ne[idx] = h[a] , h[a] = idx ++ ;
}

void Tarjan(int x)
{
    dfn[x] = low[x] = ++ ts;
    stk[++ top] = x , in_stk[x] = 1;

    for( int i = h[x] ; ~i ; i = ne[i] )
    {
        int j = e[i];
        if(!dfn[j])
        {
            Tarjan(j);
            low[x] = min(low[x] , low[j]);
        }
        else if(in_stk[j]) low[x] = min(low[x] , dfn[j]);
    }

    if(low[x] == dfn[x])
    {
        int y; ++ cnt;
        do{
            y = stk[top --] , in_stk[y] = 0;
            scc[y] = cnt;
            ++ sizes[cnt];
        }while(y != x);
    }
}