Painting Graph

問題文

頂点に $1$ から $N$ までの番号がついた $N$ 頂点 $M$ 辺の単純有向グラフが与えられます。$i$ 本目 $(1 \leq i \leq M)$ の辺は頂点 $A_i$ から頂点 $B_i$ に伸びています。

はじめ、すべての頂点は色 $0$ で塗られています。

これから $Q$ 回の操作を行います。 $i$ 回目 $(1 \leq i \leq Q)$ の操作では、頂点 $X_i$ から辺を $0$ 本以上たどって到達可能なすべての頂点を色 $Y_i$ で塗り替えます。

すべての操作を行ったあとの各頂点の色を出力してください。

制約

• $1 \leq N \leq 2 \times 10^5$
• $0 \leq M \leq 2 \times 10^5$
• $1 \leq A_i , B_i \leq N \ (1 \leq i \leq M)$
• 与えられるグラフは単純
• $1 \leq Q \leq 2 \times 10^5$
• $1 \leq X_i \leq N\ (1 \leq i \leq Q)$
• $1 \leq Y_i \leq Q\ (1 \leq i \leq Q)$
• 入力される値はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

出力

すべての操作を行ったあとの頂点 $i$ の色を $C_i$ として、以下の形式で出力せよ。

サンプル

入力

8 8
1 4
1 2
4 5
5 2
3 2
5 6
3 6
7 8
3
3 1
8 2
4 3

出力

0 3 1 3 3 3 0 2

はじめ、すべての頂点は色 $0$ で塗られています。

• $1$ 回目の操作では、頂点 $2,3,6$ を色 $1$ で塗り替えます。
• $2$ 回目の操作では、頂点 $8$ を色 $2$ で塗り替えます。
• $3$ 回目の操作では、頂点 $2,4,5,6$ を色 $3$ で塗り替えます。

以上より、すべての操作が終了したあとの各頂点の色は順に $0,3,1,3,3,3,0,2$ となります。