{"trustable":false,"sections":[{"title":"Problem Description","value":{"format":"MD","content":"We are given a connected, undirected graph *G* on *n* vertices. There is a mobile robot on one of the vertices; this vertex is labeled *s*. Each of several other vertices contains a single movable obstacle. The robot and the obstacles may only reside at vertices, although they may be moved across edges. No vertex may ever contain more than one movable entity (robot or obstacles).\nIn one step, we may move either the robot or one of the obstacles from its current position *v* to a vacant vertex adjacent to *v*. Our goal is to move the robot to a designated vertex *t* using the smallest number of steps possible.\nIn this problem, we restrict the graph *G* to be a tree, to simplify matters.\n\nHere are some examples (gray circles represent obstacles).\n\n## Example 1 (s\u003d1, t\u003d3):\n\nMove the obstacle from 2 to 4, and then move the robot through 1-2-3. Totally there are 3 moves.\n\n## Example 2 (s\u003d1, t\u003d4):\n\nMovements: 2-\u003e5, then 3-\u003e2-\u003e6, then 1-\u003e2-\u003e3-\u003e4, totally 6 moves.\n\n## Example 3 (s\u003d1, t\u003d5):\n\nMovements: 1-\u003e6, 2-\u003e1-\u003e7, 6-\u003e1-\u003e2-\u003e8, 3-\u003e2-\u003e1-\u003e6, 4-\u003e3-\u003e2-\u003e1, 8-\u003e2-\u003e3-\u003e4-\u003e5, totally 16 moves."}},{"title":"Input","value":{"format":"MD","content":"The first line contains the number of test cases *T* (T ≤ 340). Each test case begins with four integers *n, m, s, t* (4 ≤ n ≤ 15, 0 ≤ m ≤ n - 2, 1 ≤ s, t ≤ n, s ≠ t), the number of vertices, the number of obstacles and the label of the source and target. Vertices are numbered 1 to n. The next line contains *m* different integers not equal to *s*, the vertices containing obstacles. Each of the next *n - 1* lines contains two integers *u* and *v* (1 ≤ u \u003c v ≤ n), that means there is an edge *u -- v* in the tree."}},{"title":"Output","value":{"format":"MD","content":"For each test case, print the minimum number of moves *k* in the first line. Each of the next *k* lines contains two integers *a* and *b*, that means to move the robot/obstacle from *a* to *b*. If there is no solution, print ‘-1’. If there are multiple solutions, any will do.\nPrint a blank line after each test case."}},{"title":"Sample Input","value":{"format":"MD","content":"3\n4 1 1 3\n2\n1 2\n2 3\n2 4\n6 2 1 4\n2 3\n1 2\n2 3\n3 4\n2 5\n2 6\n8 3 1 5\n2 3 4\n1 2\n2 3\n3 4\n4 5\n1 6\n1 7\n2 8"}},{"title":"Sample Output","value":{"format":"MD","content":"Case 1: 3\n2 4\n1 2\n2 3\n\nCase 2: 6\n2 5\n3 2\n2 6\n1 2\n2 3\n3 4\n\nCase 3: 16\n1 6\n2 1\n1 7\n6 1\n1 2\n2 8\n3 2\n2 1\n1 6\n4 3\n3 2\n2 1\n8 2\n2 3\n3 4\n4 5"}}]}