{"problem":{"name":"Good Vertices","description":{"content":"We have a directed graph with $N$ vertices. The $N$ vertices are called Vertex $1$, Vertex $2$, $\\ldots$, Vertex $N$. At time $0$, the graph has no edge. For each $t = 1, 2, \\ldots, T$, at time $t$, a","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc236_g"},"statements":[{"statement_type":"Markdown","content":"We have a directed graph with $N$ vertices. The $N$ vertices are called Vertex $1$, Vertex $2$, $\\ldots$, Vertex $N$. At time $0$, the graph has no edge.\nFor each $t = 1, 2, \\ldots, T$, at time $t$, a directed edge from Vertex $u_t$ to Vertex $v_t$ will be added. (The edge may be a self-loop, that is, $u_t = v_t$ may hold.)\nA vertex is called _good_ when it can be reached by starting at Vertex $1$ and traversing an edge **exactly** $L$ times.\nFor each $i = 1, 2, \\ldots, N$, print the earliest time when Vertex $i$ is good. If there is no time when Vertex $i$ is good, print $-1$ instead.\n\n## Constraints\n\n*   $2 \\leq N \\leq 100$\n*   $1 \\leq T \\leq N^2$\n*   $1 \\leq L \\leq 10^9$\n*   $1 \\leq u_t, v_t \\leq N$\n*   $i \\neq j \\Rightarrow (u_i, v_i) \\neq (u_j, v_j)$\n*   All values in input are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $T$ $L$\n$u_1$ $v_1$\n$u_2$ $v_2$\n$\\vdots$\n$u_T$ $v_T$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc236_g","tags":[],"sample_group":[["4 5 3\n2 3\n3 4\n1 2\n3 2\n2 2","\\-1 4 5 3\n\nAt time $0$, the graph has no edge. Afterward, edges are added as follows.\n\n*   At time $1$, a directed edge from Vertex $2$ to Vertex $3$ is added.\n*   At time $2$, a directed edge from Vertex $3$ to Vertex $4$ is added.\n*   At time $3$, a directed edge from Vertex $1$ to Vertex $2$ is added. Now, Vertex $4$ can be reached from Vertex $1$ in exactly three moves: $1 \\rightarrow 2 \\rightarrow 3 \\rightarrow 4$, making Vertex $4$ good.\n*   At time $4$, a directed edge from Vertex $3$ to Vertex $2$ is added. Now, Vertex $2$ can be reached from Vertex $1$ in exactly three moves: $1 \\rightarrow 2 \\rightarrow 3 \\rightarrow 2$, making Vertex $2$ good.\n*   At time $5$, a directed edge (self-loop) from Vertex $2$ to Vertex $2$ is added. Now, Vertex $3$ can be reached from Vertex $1$ in exactly three moves: $1 \\rightarrow 2 \\rightarrow 2 \\rightarrow 3$, making Vertex $3$ good.\n\nVertex $1$ will never be good."],["2 1 1000000000\n1 2","\\-1 -1"]],"created_at":"2026-03-03 11:01:14"}}