Fechamento das Estações
Uma companhia administra n estações e m rotas direcionadas. Uma estação sem nenhuma rota de saída fecha no dia 0. Em cada dia inteiro seguinte, uma estação que ainda está aberta fecha se todas as estações às quais ela tem rotas diretas já estavam fechadas no dia anterior. As decisões de fechamento de um mesmo dia são simultâneas.
Determine para cada estação o dia em que fecha. Algumas estações podem permanecer abertas para sempre. Rotas repetidas e rotas de uma estação para ela própria são permitidas.
Input
A primeira linha contém n m. Cada uma das próximas m linhas contém uma rota u v.
Restrições:
1 ≤ n ≤ 200000; 0 ≤ m ≤ 200000; 1 ≤ u,v ≤ n.
Output
Imprima n inteiros: para cada estação i, o dia de seu fechamento, ou -1 caso nunca feche.
Samples
Sample 1
Input
5 5 1 2 1 3 2 4 3 4 5 5
Output
2 1 1 0 -1
A estação 4 fecha no dia 0; as estações 2 e 3 no dia 1; a estação 1 no dia 2. A estação 5 nunca fecha por ter uma rota para si mesma.