{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"Hanzo Hattori rescued Princess Nakururu and now they are planning to escape from the castle, because it\u0027s going to explode. Now the problem is that Nakururu is not quite well that\u0027s why she can\u0027t run all the way. And Hattori is also injured. That\u0027s why he can\u0027t carry her all the way.\n\nSo, they made a plan. From their current position, Hanzo will carry Nakururu to the next place. Then they both will run to the next place. Then again Hanzo will carry Nakururu to the next place. And they will continue this procedure to go from one place to another.\n\nEach place can be treated as a node. Nodes are connected by bi-directional roads. All the nodes are numbered as integers. Initially they are at node **1**. And both of them will run to the next node.\n\nNow given the description of the nodes and roads you have to count the number of possible nodes which can be entered by Hanzo carrying Nakururu with him. Initially Hattori doesn\u0027t carry Nakururu."}},{"title":"Input","value":{"format":"MD","content":"Input starts with an integer **T (\u0026le; 210)**, denoting the number of test cases.\n\nEach case starts with a blank line. The next line will contain two integers: **n (1 \u0026le; n \u0026le; 100)** and **m (0 \u0026le; m \u0026le; n*(n-1)/2)**, indicating the number of nodes and the number of roads respectively. The next **m** lines, each will contain two integers **a** **b (1 \u0026le; a, b \u0026le; n, a \u0026ne; b)** indicating that there is a road between node **a** and **b**. All the given roads will be distinct."}},{"title":"Output","value":{"format":"MD","content":"For each case, print the case number and number of nodes that can be entered by Hanzo, carrying Nakururu with him."}},{"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\n\n4 3\n1 2\n2 3\n3 4\n\n5 4\n1 2\n2 3\n1 3\n3 4\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase 1: 2\nCase 2: 4\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}