{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"The cows have been sent on a mission through space to acquire a new milking machine for their barn. They are flying through a cluster of stars containing N (1 \u0026lt;\u003d N \u0026lt;\u003d 50,000) planets, each with a trading post.\r\u003cbr\u003e\r\u003cbr\u003eThe cows have determined which of K (1 \u0026lt;\u003d K \u0026lt;\u003d 1,000) types of objects (numbered 1..K) each planet in the cluster desires, and which products they have to trade. No planet has developed currency, so they work under the barter system: all trades consist of each party trading exactly one object (presumably of different types).\r\u003cbr\u003e\r\u003cbr\u003eThe cows start from Earth with a canister of high quality hay (item 1), and they desire a new milking machine (item K). Help them find the best way to make a series of trades at the planets in the cluster to get item K. If this task is impossible, output -1."}},{"title":"Input","value":{"format":"HTML","content":"* Line 1: Two space-separated integers, N and K.\r\u003cbr\u003e\r\u003cbr\u003e* Lines 2..N+1: Line i+1 contains two space-separated integers, a_i and b_i respectively, that are planet i\u0027s trading trading products. The planet will give item b_i in order to receive item a_i."}},{"title":"Output","value":{"format":"HTML","content":"* Line 1: One more than the minimum number of trades to get the milking machine which is item K (or -1 if the cows cannot obtain item K).\r\u003cbr\u003e\r\u003cbr\u003e* Lines 2..T+1: The ordered list of the objects that the cows possess in the sequence of trades."}},{"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\u003e6 5\r\n1 3\r\n3 2\r\n2 3\r\n3 1\r\n2 5\r\n5 4\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e4\r\n1\r\n3\r\n2\r\n5\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Hint","value":{"format":"HTML","content":"OUTPUT DETAILS:\r\u003cbr\u003e\r\u003cbr\u003eThe cows possess 4 objects in total: first they trade object 1 for object 3, then object 3 for object 2, then object 2 for object 5."}}]}