B. Aquapark Graph
time limit per test
7 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You have a dynamic graph on $$$n$$$ vertices. The graph is described by an array $$$a$$$: vertex $$$i$$$ has an edge to $$$a_i$$$. Initially, $$$a_i=i$$$ for all $$$i$$$.

You are given $$$q$$$ triples ($$$u$$$,$$$x$$$,$$$s$$$). For each of them, do the following:

  • $$$a_u=x$$$ (delete the old edge $$$u \rightarrow a_u$$$ and add a new edge $$$u \rightarrow a_u=x$$$)
  • Start a new walk from vertex $$$s$$$. We walk along directed edges. After each move, we check whether we have visited this vertex earlier in the same walk; if so, we stop. Find the number of steps we took.
Input

The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n,q \le 2\cdot 10^5$$$) — the number of vertices and the number of queries, respectively.

Each of the following $$$q$$$ lines contains three integers $$$u,x,s$$$ ($$$1 \le u,x,s \le n$$$) — parameters of a query.

Output

For each query, output a single integer — the number of steps of the walk.

Example
Input
8 7
1 2 2
2 3 1
3 1 1
1 7 1
7 2 1
5 3 5
6 2 6
Output
1
3
3
2
4
5
5