{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003e\u003ccenter\u003e\u003cimg style\u003d\"max-width:100%;\" src\u003d\"CDN_BASE_URL/d9c6fc71f3c0e0c44f0462bc782fef94?v\u003d1714950250\"\u003e\u003c/center\u003e\u003cbr\u003eInkopolis is the city in which Inklings live in, it can be regarded as an undirected connected graph with exactly $N$ vertices and $N$ edges between vertices. It is guaranteed that the graph doesn’t contain duplicated edges or self loops. Inklings can splatter a special type of colored ink to decorate the roads they live in. Inklings are capricious so they often change the color of the roads to celebrate the upcoming Splatfest.\u003cbr\u003eThe Splatfest lasts for exactly $M$ days, on each day Inklings will splatter ink on exactly one road, the color on this road will be coverd by the new color of the ink. At the end of each day, they wonder how many different colored regions are there in the Inkopolis. A colored region is a set of connected roads with same color, to be clear, two roads are in the same colored region if they have the same color and share a common vertex.\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The first line of the input gives the number of test cases, $T$. $T$ test cases follow.\u003cbr\u003eFor each test case, the first line contains two integers $N$ and $M$, where $N$ is the number of vertexes and roads in Inkopolis, and $M$ is the number of days that Splatfest lasts.\u003cbr\u003eFollowing $N$ lines describe the roads between the vertexes. Each line contains 3 integers $x$, $y$, $c$, representing there is a road with color $c$ between the $x^{th}$ and the $y^{th}$ vertex.\u003cbr\u003eNext following $M$ lines describe the operations on each day. Each line contains 3 integers $x$, $y$, $c$, representing an operation that Inklings splatter the ink with color $c$ to the road between the $x^{th}$ and the $y^{th}$ vertex, it is guaranteed that there is such a road.\u003cbr\u003e$1 \\leq T \\leq 100$\u003cbr\u003e$3 \\leq N \\leq 2 \\times 10^5$\u003cbr\u003e$1 \\leq M \\leq 2 \\times 10^5$\u003cbr\u003e$1 \\leq x, y, c \\leq n$\u003cbr\u003e$\\sum N, \\sum M \\leq 10^6$"}},{"title":"Output","value":{"format":"HTML","content":"For each test case, output one line containing “Case #x:” first, where $x$ is the test case number (starting from 1).\u003cbr\u003eThe following $M$ lines each consists of an integer which is the number of colored regional in Inkopolis after each day."}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\r\n4 3\r\n4 2 4\r\n2 3 3\r\n3 4 2\r\n1 4 1\r\n3 4 2\r\n2 3 4\r\n3 4 3\r\n4 4\r\n1 2 1\r\n2 3 1\r\n3 4 1\r\n4 1 1\r\n1 2 2\r\n3 4 2\r\n2 3 2\r\n4 1 4\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase #1:\r\n4\r\n3\r\n3\r\nCase #2:\r\n2\r\n4\r\n2\r\n2\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}