{"raw_statement":[{"iden":"problem statement","content":"You are given a simple undirected graph with $N$ vertices and $M$ edges. The $N$ vertices are called Vertex $1$, Vertex $2$, $\\ldots$, Vertex $N$.  \nFor each $i = 1, 2, \\ldots, M$, the $i$\\-th edge connects Vertex $u_i$ and Vertex $v_i$.  \nAdditionally, for each $i = 1, 2, \\ldots, N$, Vertex $i$ has an integer $i$ written on it.\nYou are also given $Q$ queries.  \nFor each $i = 1, 2, \\ldots, Q$, the $i$\\-th query is represented as an integer $x_i$. This query involves the following operation.\n\n1.  Let $X$ be the integer written on Vertex $x_i$.\n2.  For every vertex adjacent to Vertex $x_i$, replace the integer written on it with $X$.\n\nHere, Vertex $u$ and Vertex $v$ are said to be adjacent when there is an edge connecting them.\nPrint the integer written on each vertex after all queries are processed in the order they are given from input."},{"iden":"constraints","content":"*   $1 \\leq N \\leq 2 \\times 10^5$\n*   $0 \\leq M \\leq \\min(2 \\times 10^5, N(N-1)/2)$\n*   $1 \\leq Q \\leq 2 \\times 10^5$\n*   $1 \\leq u_i, v_i \\leq N$\n*   $1 \\leq x_i \\leq N$\n*   The given graph is simple. In other words, it has no self-loops and no multi-edges.\n*   All values in input are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$ $M$ $Q$\n$u_1$ $v_1$\n$u_2$ $v_2$\n$\\vdots$\n$u_M$ $v_M$\n$x_1$ $x_2$ $\\ldots$ $x_Q$"},{"iden":"sample input 1","content":"5 6 3\n4 2\n4 3\n1 2\n2 3\n4 5\n1 5\n1 3 4"},{"iden":"sample output 1","content":"1 3 3 3 3\n\nEach query involves the following operation.\n\n*   The first query $(x_1 = 1)$: Vertex $1$ has the integer $1$ written on it, and the vertices adjacent to Vertex $1$ are Vertices $2$ and $5$. Thus, the integers on Vertices $2$ and $5$ get replaced with $1$.\n*   The second query $(x_2 = 3)$: Vertex $3$ has the integer $3$ written on it, and the vertices adjacent to Vertex $3$ are Vertices $2$ and $4$. Thus, the integers on Vertices $2$ and $4$ get replaced with $3$.\n*   The third query $(x_3 = 4)$: Vertex $4$ has the integer $3$ written on it, and the vertices adjacent to Vertex $4$ are Vertices $2$, $3$, and $5$. Thus, the integers on Vertices $2$, $3$, and $5$ get replaced with $3$. (Vertices $2$ and $3$ already have $3$ written on them, so the actual change takes place only on Vertex $5$.)"},{"iden":"sample input 2","content":"14 14 8\n7 4\n13 9\n9 8\n4 3\n7 2\n13 8\n12 8\n11 3\n6 3\n7 14\n6 5\n1 4\n10 13\n5 2\n2 6 12 9 1 10 5 4"},{"iden":"sample output 2","content":"1 6 1 1 6 6 1 9 9 10 11 12 10 14"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}