{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n #problem-body \u003e pre {\n display: block;\n padding: 9.5px;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n word-break: break-all;\n word-wrap: break-word;\n color: #333;\n background: rgba(255, 255, 255, 0.5);\n border: 1px solid #ccc;\n border-radius: 6px;\n }\n\u003c/style\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv id\u003d\"problem-body\"\u003e\n\t\u003cp\u003eAda the Ladybug and her friends are on trip in Bugraine. Most of them are in different cities at the moment. They want to spread as much as possible, make hologram-skype to show all others the city. They have agreed, to make this call in time \u003cstrong\u003eT\u003c/strong\u003e.\u003c/p\u003e\r\n\u003cp\u003eThe cities are connected with bi-directional roads. Each of the road has some length (which equals to time it takes to travel between two cities).\u003c/p\u003e\r\n\u003ch3\u003eInput\u003c/h3\u003e\r\n\u003cp\u003eThe first line will contain the number of test-cases.\u003c/p\u003e\r\n\u003cp\u003eThe first line of each test-case begins with four integers: \u003cstrong\u003eN, M, F, T\u003c/strong\u003e, number of cities, number of roads, number of friends (Ada inclusive) and time they have: \u003cstrong\u003e1 ≤ N, F ≤ 500\u003c/strong\u003e, \u003cstrong\u003e 0 ≤ M ≤ 10\u003csup\u003e5\u003c/sup\u003e, 0 ≤ T ≤ 5*10\u003csup\u003e8\u003c/sup\u003e\u003c/strong\u003e\u003c/p\u003e\r\n\u003cp\u003eThen a line with \u003cstrong\u003eF\u003c/strong\u003e integers follows, \u003cstrong\u003e 1 ≤ H\u003csub\u003ei\u003c/sub\u003e ≤ N\u003c/strong\u003e, the city, where \u003cstrong\u003ei\u003c/strong\u003e\u003csup\u003eth\u003c/sup\u003e friend currently is.\u003c/p\u003e\r\n\u003cp\u003eAfterward \u003cstrong\u003eM\u003c/strong\u003e lines follow, with three integers \u003cstrong\u003eA, B, L\u003c/strong\u003e, \u003cstrong\u003e1 ≤ A, B ≤ N, 1 ≤ L ≤ 10\u003csup\u003e6\u003c/sup\u003e\u003c/strong\u003e, indicating a road, which connect cities \u003cstrong\u003eA, B\u003c/strong\u003e with length of \u003cstrong\u003eL\u003c/strong\u003e\u003c/p\u003e\r\n\u003cp\u003ePS: There might exist multiple roads between two cities and there might also be a \"circular route\" which begins and ends in the same city!\u003c/p\u003e\r\n\u003ch3\u003eOutput\u003c/h3\u003e\r\n\u003cp\u003eFor each test-case, print maximal number of different cities Ada and her friends can end up at after \u003cstrong\u003eT\u003c/strong\u003e time!\u003c/p\u003e\r\n\u003ch3\u003eExample\u003c/h3\u003e\u003ctable class\u003d\"vjudge_sample\"\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\u003e3\r\n5 5 4 3\r\n1 1 1 1\r\n1 2 3\r\n1 5 2\r\n5 4 2\r\n4 3 1\r\n2 3 2\r\n7 7 6 3\r\n6 6 2 2 2 2\r\n1 7 5\r\n1 2 5\r\n7 2 4\r\n2 3 2\r\n3 4 3\r\n5 4 1\r\n2 5 2\r\n5 5 4 4\r\n1 1 1 1\r\n1 2 3\r\n1 5 2\r\n5 4 2\r\n4 3 1\r\n2 3 2\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3\r\n5\r\n4\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\r\n\u003ch3\u003eOutput Explanation\u003c/h3\u003e\r\n\u003cp\u003eIn \u003cstrong\u003efirst\u003c/strong\u003e test-case, all 4 friends begin in same node. From this node, one can get to nodes \u003cstrong\u003e2\u003c/strong\u003e and \u003cstrong\u003e5\u003c/strong\u003e, or stay in the node (in time ≤ 3). Since everyone is in node 1, best they can do is to choose one friend who goes to 5, one who goes to 2 and the rest of them can stay so with \"1, 1, 2, 5\" they can occupy 3 different nodes (at most).\u003c/p\u003e\r\n\u003cp\u003eIn \u003cstrong\u003esecond\u003c/strong\u003e test-case, friends on \u003cstrong\u003e6\u003c/strong\u003e can go nowhere (just stay in 6). Friends on 2 can go to \u003cstrong\u003e3, 4, 5\u003c/strong\u003e or stay on \u003cstrong\u003e2\u003c/strong\u003e. So with friends in \u003cstrong\u003e6, 6, 2, 3, 4, 5\u003c/strong\u003e we get maximum of 5 different cities.\u003c/p\u003e\r\n\u003cp\u003eLast (\u003cstrong\u003ethird\u003c/strong\u003e) test-case is same as first - except for time. This one additional time-unit will let friends go to \u003cstrong\u003e4\u003c/strong\u003e (or to nodes which they can go in first test-case). \"1, 2, 4, 5\" would make 4 different cities!\u003c/p\u003e\n\u003c/div\u003e"}}]}