{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"Background\r\u003cbr\u003e\r\u003cbr\u003eOn its trip, a train has to pass a lot of points (American English: switches) and signals. The train抯 track depends on the status of points and signals. The responsible operator on the signal box does not handle them separately, but tells the signal box the start and destination signal of the train抯 journey. The box then determines the correct status of points and signals and brings them into the right position. \r\u003cbr\u003e\u003ccenter\u003e\u003cimg src\u003d\"CDN_BASE_URL/b44c519eb00d0f4479929b0085840b42?v\u003d1726804013\"\u003e\u003c/center\u003e\r\u003cbr\u003e\r\u003cbr\u003eFigure 9 shows a sample scenario in which railway tracks are shown as solid lines and signals are drawn as triangles (this is also the first scenario of the sample input). Signals have a sense of direction: they are only valid for the direction in which the triangle points (e.g., signal A is valid for trains running from left to right, see also Figure 10). Points are located where railway tracks meet (e.g., at points W1, W2, etc.). Points have a front side (i.e., the side from which a train can take alternative directions) and a back side and can be in two positions, named + and -. If a train comes from the front side, it leaves the point at the + or - leg, dependent on the point抯 position (see Figure 11). If the train comes from one of the the back legs, it leaves it at the front leg. Even then the point has to be put into the right state, otherwise it gets damaged! \r\u003cbr\u003e\r\u003cbr\u003e\u003ccenter\u003e\u003cimg src\u003d\"CDN_BASE_URL/1d7b76f6e60f085da110099e574c75c3?v\u003d1726804013\"\u003e\u003c/center\u003e\r\u003cbr\u003e\r\u003cbr\u003eProblem\r\u003cbr\u003e\r\u003cbr\u003eYour task is to implement an automatic signal box, i.e., write a program which finds the correct position of points and signals for a given start and destination. The signal box should follow these rules:\r\u003cbr\u003e\r\u003cbr\u003eA journey can only start and end at a signal. Both signals have to be in the same direction!\r\u003cbr\u003e\r\u003cbr\u003eDuring a journey a train must not change its direction.\r\u003cbr\u003e\r\u003cbr\u003eThe journey consists of a sequence of signal and point settings. A signal is only taken into account for the journey if it has the right direction. A point along the way is always taken into account. \r\u003cbr\u003e\r\u003cbr\u003eIf there is more than one possible track from the start signal to the destination signal, the correct one is determined by the following scheme:\r\u003cbr\u003e\r\u003cbr\u003eConsider a set of path selection rules. These are given as a triple (x, y, z) of point identifiers x and y, and a position z. A selection rule has the following meaning:\r\u003cbr\u003e\r\u003cbr\u003e\r\u003cbr\u003eIf there are alternative paths starting at point x and ending at point y where x is approached from the front and y from the back, then consider only paths in which x is in position z (z is either + or -).\r\u003cbr\u003e\r\u003cbr\u003eIf no such rule exists for a given point x, the - position must be chosen.\r\u003cbr\u003e\r\u003cbr\u003eThe sample in- and output demonstrate the application of the rules. Furthermore, you can make the following assumptions:\r\u003cbr\u003e\r\u003cbr\u003eThe track plan is acyclic.\r\u003cbr\u003e\r\u003cbr\u003eWithin a path, each element is only used once or not at all.\r\u003cbr\u003e\r\u003cbr\u003eIf for a given point x several rules (x, y, z) exist, they will agree on the position to be chosen.\r\u003cbr\u003e\r\u003cbr\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The first line contains the number of scenarios.\r\u003cbr\u003e\r\u003cbr\u003eIn the first line of the input for every scenario, you are given two signal identifiers for the departure and the destination, separated by a single blank. The following line contains the number n of elements (points and signals) in the track plan. You can assume 1\u0026lt;\u003dn\u0026lt;\u003d200 and that each element has a unique identifier of at most 20 alphanumeric characters. The identifier \"XXX\" is given to track ends.\r\u003cbr\u003e\r\u003cbr\u003eThere are signal and point elements, given in the following format:\r\u003cbr\u003e\r\u003cbr\u003ePoints are specified by a line \"W I F M P\" where W stands for \"Weiche\" (German for point), I is the identifier of the point, F identifies the front element of the point, and M and P give the identifiers of the back elements of the point depending on whether it is in minus or plus position.\r\u003cbr\u003e\r\u003cbr\u003eSignals are specified by a line \"S I F B\" where S stands for \"Signal\" (German for signal), I is the identifier of the signal, and F and B give the identifiers of the front and back elements of the signal.\r\u003cbr\u003e\r\u003cbr\u003eThe direction for which the signal is valid is from front to back.\r\u003cbr\u003e\r\u003cbr\u003eThe following line contains the number p, 0\u0026lt;\u003dp\u0026lt;\u003d100, of path selection rules, followed by another p lines of the rules themselves. A rule is of the form \"FW X Y Z\" where FW is the identifier of \"Fahrstrabenwahl-Regel\" (German for path selection rule), X, Y and Z are the elements of the rule as explained above.\r\u003cbr\u003e"}},{"title":"Output","value":{"format":"HTML","content":"The output for every scenario begins with a line containing \"Scenario #i:\", where i is the number of the scenario starting at 1.\r\u003cbr\u003e\r\u003cbr\u003eFor every scenario print out the elements on the path from departure to destination in the order they are passed by the train. However, print the signals first, followed by the points. Every element of the path must be on a line by itself. Elements of the path are signal and point identifiers (the first and the last signal identifiers must also be printed). For every point you should also give the correct position of the point as either + or - on the same line, separated from the point identifier by a single blank. If there is no possible path, print \"NOT POSSIBLE\".\r\u003cbr\u003e\r\u003cbr\u003eTerminate each scenario by a blank line."}},{"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\u003e4\r\nA AC\r\n14\r\nS AB A XXX\r\nS A AB W1\r\nW W1 A W2 P3\r\nW W2 W1 P1 P2\r\nS P1 N1 W2\r\nS N1 P1 W11\r\nW W11 F N1 W12\r\nS F AC W11\r\nS AC F XXX\r\nS P2 N2 W2\r\nS N2 P2 W12\r\nW W12 W11 N3 N2\r\nS P3 N3 W1\r\nS N3 P3 W12\r\n2\r\nFW W1 W11 +\r\nFW W11 W1 -\r\nS1 S2\r\n2\r\nS S1 S2 XXX\r\nS S2 S1 XXX\r\n0\r\nS1 S4\r\n6\r\nS S1 XXX W1\r\nS S2 W1 XXX\r\nS S3 XXX W2\r\nS S4 W2 XXX\r\nW W1 S1 S2 W2\r\nW W2 S4 W1 S3\r\n0\r\nS1 S2\r\n8\r\nS S1 XXX W1\r\nS S2 W4 XXX\r\nS S3 W1 W2\r\nS S4 W3 W4\r\nW W1 S1 W2 S3\r\nW W2 W3 W1 S3\r\nW W3 W2 W4 S4\r\nW W4 S2 W3 S4\r\n1\r\nFW W1 W2 +\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eScenario #1:\r\nA\r\nN3\r\nAC\r\nW1 +\r\nW12 -\r\nW11 +\r\n\r\nScenario #2:\r\nNOT POSSIBLE\r\n\r\nScenario #3:\r\nS1\r\nS4\r\nW1 +\r\nW2 -\r\n\r\nScenario #4:\r\nS1\r\nS3\r\nS2\r\nW1 +\r\nW2 +\r\nW3 -\r\nW4 -\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}