{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\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 type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eThe year is 3019. By now the humanity is living in cities floating in the atmosphere on air balloons and jet engines. There are $$$n$$$ cities on the planet connected by the jet trains network. If the cities $$$a$$$ and $$$b$$$ are connected by the train route, people can travel between them in any direction. The $$$a$$$-th city can be reached from the $$$b$$$-th city if and only if there is a path between $$$a$$$ and $$$b$$$, where each edge of the path represent a train route.\u003c/p\u003e\u003cp\u003ePeople of 3019 love to be friends, and it happens so people from the same city have many friends in common. Let us say that the friendship connects not pairs of people, but pairs of cities. The friendship of two cities is mutual.\u003c/p\u003e\u003cp\u003eSometimes people from a city may decide to organize a celebration and invite all the people from friendly cities. If the celebration is announced to be in city $$$a$$$, all people from the friendly cities of $$$a$$$ try to get to $$$a$$$ using jet trains network. People from all friendly cities of $$$a$$$ that can reach the city $$$a$$$ join the celebration.\u003c/p\u003e\u003cp\u003eIt has been decided to create a special system called \"Celebration 3019\" to evaluate the number of people on a certain celebration. There is information about cities which are friends, and the current state of the jet trains network. The system must handle the following requests: \"If the celebration is announced in the city $$$v$$$, people from how many cities will attend it?\". Besides, there should be an option to add an information about new pair of friendly cities, and about new jet train route. Fortunately, the train routes never cancel and once friended, the cities remain friends forever.\u003c/p\u003e\u003cp\u003ePlease help the mankind to develop such a system.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line contains three integers $$$n$$$, $$$m$$$, $$$k$$$ — number of cities, number of pairs of friendly cities and number of jet trains routes ($$$1 \\le n \\le 10^5$$$, $$$0 \\le m, k \\le 10^5$$$). \u003c/p\u003e\u003cp\u003eThe following $$$m$$$ lines contain two integers $$$a$$$ and $$$b$$$ each ($$$1 \\le a, b \\le n$$$, $$$a \\neq b$$$) — pairs of friendly cities. It is guaranteed that each pair is listed at most once.\u003c/p\u003e\u003cp\u003eThe following $$$k$$$ lines contain two integers $$$a$$$, $$$b$$$ ($$$1 \\le a, b \\le n$$$, $$$a \\neq b$$$) — pairs of cities connected by the jet train routes. There is at most one route between each pair of cities.\u003c/p\u003e\u003cp\u003eThe next line contains the integer $$$q$$$ ($$$0 \\le q \\le 10^5$$$) — the number of requests to handle, and the following $$$q$$$ lines represent requests. \u003c/p\u003e\u003cul\u003e \u003cli\u003e Request \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eT\u003c/span\u003e $$$a$$$ $$$b$$$\" means that there is now a jet train route between $$$a$$$ and $$$b$$$ ($$$1 \\le a, b \\le n$$$, $$$a \\neq b$$$). It is guaranteed that there was no direct route between $$$a$$$ and $$$b$$$ before the request. \u003c/li\u003e\u003cli\u003e Request \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eF\u003c/span\u003e $$$a$$$ $$$b$$$\" means that $$$a$$$ and $$$b$$$ are friends now ($$$1 \\le a, b \\le n$$$, $$$a \\neq b$$$). It is guaranteed that $$$a$$$ and $$$b$$$ were not friends before the request. \u003c/li\u003e\u003cli\u003e Request \"\u003cspan class\u003d\"tex-font-style-tt\"\u003e?\u003c/span\u003e $$$v$$$\" means that a request is made to the system: \"If the celebraion is announced in the city $$$v$$$, people from how many cities will attend it?\" ($$$1 \\le v \\le n$$$) \u003c/li\u003e\u003c/ul\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eFor each request \"\u003cspan class\u003d\"tex-font-style-tt\"\u003e?\u003c/span\u003e $$$v$$$\" print the answer to it on a new line.\u003c/p\u003e"}},{"title":"Examples","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\u003e4 2 2\n1 2\n1 3\n1 2\n1 4\n5\n? 1\nF 4 1\n? 1\nT 4 3\n? 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\n2\n3\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003eThe answer to the first request equals one, because only one of the cities $$${2, 3}$$$ has a train route to the city $$$1$$$. The answer to the second request equals two, because before the request cities $$$1$$$ and $$$4$$$ became friends, and they had a train route connecting them. The answer to the third request equals three, because there is now possible to travel from the city $$$3$$$ to the city $$$1$$$ using trains network: first, people can travel to city $$$4$$$, and then to city $$$1$$$.\u003c/p\u003e"}}]}