問題一覧 > 通常問題

No.3784 01 Walk

レベル : / AI推定難易度 : 2200 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 1024 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 6
作問者 : askr58 / テスター : 👑 AngrySadEight / テストしたAI : claude-opus-5-5
お気に入りにしたユーザー ProblemId : 13591 / 自分の提出
問題文最終更新日: 2026-10-26 05:26:22
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 520 (順位表) の他の問題:

Problem Statement

There is a directed graph with $N$ vertices and $M$ edges. The vertices are numbered with integers from $1$ to $N$, and the edges are numbered with integers from $1$ to $M$. For $1\le i\le M$, edge $i$ is directed from vertex $u_i$ to vertex $v_i$ and has an integer $c_i$ written on it. Here, $c_i \in \{0,1\}$. Initially, a piece is placed on vertex $1$.

There is a sequence $A$, and initially $A$ is empty. You may now perform the following operation any number of times, $0$ or more.

  • Suppose the piece is currently on vertex $x$. Choose $1$ edge $e$ such that $u_e=x$, and move the piece to vertex $v_e$. Then, if $A$ is empty or the last element of $A$ differs from $c_e$, append the integer $c_e$ to the end of $A$. Otherwise, (without performing the operation of appending $c_e$) delete the current last element of $A$.

However, if the out-degree of vertex $x$ is $0$, the operation cannot be performed.

For each of $k=1,2,\cdots ,N$, find the maximum possible length of $A$ in a state where the piece is on vertex $k$. If the maximum does not exist, output -1 instead. Note that the constraints guarantee that, for every vertex $v$ with $1\le v\le N$, vertex $v$ is reachable from vertex $1$; that is, there exists a sequence of operations that places the piece on vertex $v$.

Constraints

  • $1\le N\le 2\times 10^5$
  • $0\le M\le 2\times 10^5$
  • $1\le u_i,v_i\le N\ (1\le i\le M)$
  • $c_i \in \{0,1\}\ (1\le i\le M)$
  • $(u_i,v_i,c_i) \neq (u_j,v_j,c_j)\ (1\le i < j\le M)$
  • For every vertex $v$ with $1\le v\le N$, vertex $v$ is reachable from vertex $1$
  • All input values are integers

Input

The input is given in the following format.

$N\ M$
$u_1\ v_1\ c_1$
$u_2\ v_2\ c_2$
$\vdots$
$u_M\ v_M\ c_M$

Output

Output $N$ lines. On the $i$-th line $(1\le i\le N)$, output the maximum length of $A$ in a state where the piece is on vertex $i$ (or -1 if it does not exist). Print a newline at the end.

Sample

Sample 1
Input
6 7
1 2 1
2 3 0
3 4 1
4 2 0
1 5 1
5 6 1
6 5 0
Output
0
4
3
3
-1
-1

For example, the following operations achieve a length of $3$ for $A$ with the piece on vertex $3$.

  • Choose edge $1$ and move the piece from vertex $1$ to vertex $2$. Now $A=(1)$.
  • Choose edge $2$ and move the piece from vertex $2$ to vertex $3$. Now $A=(1,0)$.
  • Choose edge $3$ and move the piece from vertex $3$ to vertex $4$. Now $A=(1,0,1)$.
  • Choose edge $4$ and move the piece from vertex $4$ to vertex $2$. Now $A=(1,0,1,0)$.
  • Choose edge $2$ and move the piece from vertex $2$ to vertex $3$. Now $A=(1,0,1)$.

Also, by first choosing edge $5$ and then alternately choosing edge $6$ and edge $7$, the length of $A$ can be made arbitrarily large while moving the piece between vertex $5$ and vertex $6$. Therefore, the answer for vertices $5,6$ is -1.

Sample 2
Input
10 13
1 2 1
2 3 1
3 4 0
4 1 0
2 7 0
3 6 1
4 10 0
10 5 1
5 6 1
6 7 0
7 8 1
8 9 1
9 5 0
Output
0
1
0
1
1
1
2
3
2
0

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。