{"problem":{"name":"Smart Infants","description":{"content":"There are $N$ infants registered in AtCoder, numbered $1$ to $N$, and $2\\times 10^5$ kindergartens, numbered $1$ to $2\\times 10^5$. Infant $i$ has a rating of $A_i$ and initially belongs to Kindergart","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":3500,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc170_e"},"statements":[{"statement_type":"Markdown","content":"There are $N$ infants registered in AtCoder, numbered $1$ to $N$, and $2\\times 10^5$ kindergartens, numbered $1$ to $2\\times 10^5$. Infant $i$ has a rating of $A_i$ and initially belongs to Kindergarten $B_i$.\nFrom now on, $Q$ transfers will happen. After the $j$\\-th transfer, Infant $C_j$ will belong to Kindergarten $D_j$.\nHere, we define the _evenness_ as follows. For each kindergarten with one or more infants registered in AtCoder, let us find the highest rating of an infant in the kindergarten. The evenness is then defined as the lowest among those ratings.\nFor each of the $Q$ transfers, find the evenness just after the transfer.\n\n## Constraints\n\n*   $1 \\leq N,Q \\leq 2 \\times 10^5$\n*   $1 \\leq A_i \\leq 10^9$\n*   $1 \\leq C_j \\leq N$\n*   $1 \\leq B_i,D_j \\leq 2 \\times 10^5$\n*   All values in input are integers.\n*   In the $j$\\-th transfer, Infant $C_j$ changes the kindergarten it belongs to.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $Q$\n$A_1$ $B_1$\n$A_2$ $B_2$\n$:$\n$A_N$ $B_N$\n$C_1$ $D_1$\n$C_2$ $D_2$\n$:$\n$C_Q$ $D_Q$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc170_e","tags":[],"sample_group":[["6 3\n8 1\n6 2\n9 3\n1 1\n2 2\n1 3\n4 3\n2 1\n1 2","6\n2\n6\n\nInitially, Infant $1, 4$ belongs to Kindergarten $1$, Infant $2, 5$ belongs to Kindergarten $2$, and Infant $3, 6$ belongs to Kindergarten $3$.\nAfter the $1$\\-st transfer that makes Infant $4$ belong to Kindergarten $3$, Infant $1$ belongs to Kindergarten $1$, Infant $2, 5$ belong to Kindergarten $2$, and Infant $3, 4, 6$ belong to Kindergarten $3$. The highest ratings of an infant in Kindergarten $1, 2, 3$ are $8, 6, 9$, respectively. The lowest among them is $6$, so the $1$\\-st line in the output should contain $6$.\nAfter the $2$\\-nd transfer that makes Infant $2$ belong to Kindergarten $1$, Infant $1, 2$ belong to Kindergarten $1$, Infant $5$ belongs to Kindergarten $2$, and Infant $3, 4, 6$ belong to Kindergarten $3$. The highest ratings of an infant in Kindergarten $1, 2, 3$ are $8, 2, 9$, respectively. The lowest among them is $2$, so the $2$\\-nd line in the output should contain $2$.\nAfter the $3$\\-rd transfer that makes Infant $1$ belong to Kindergarten $2$, Infant $2$ belongs to Kindergarten $1$, Infant $1, 5$ belong to Kindergarten $2$, and Infant $3, 4, 6$ belong to Kindergarten $3$. The highest ratings of an infant in Kindergarten $1, 2, 3$ are $6, 8, 9$, respectively. The lowest among them is $6$, so the $3$\\-rd line in the output should contain $6$."],["2 2\n4208 1234\n3056 5678\n1 2020\n2 2020","3056\n4208"]],"created_at":"2026-03-03 11:01:14"}}