{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eO mundo está em perigo! Terremotos terríveis são detectados em todo o mundo. Casas são destruídas, rios transbordam, é quase impossível se locomover de uma cidade para outra. Algumas estradas ainda são úteis, mas até elas se tornaram muito íngremes devido aos movimentos do solo.\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eFelizmente, o engenheiro Ivan tem um carro, que pode subir e descer bem. Mas existem diferentes modos de marcha para movimento para cima e para baixo, então durante a condução você tem que mudar os modos de marcha o tempo todo. Além disso, o engenheiro Ivan tem um bom amigo - o geólogo Orlov. Juntos, eles são capazes de inventar um plano para salvar o mundo. Mas, infelizmente, o geólogo Orlov mora em outra cidade.\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eIvan quer salvar o mundo, mas a caixa de câmbio do seu carro começou a desgastar, então ele não sabe por quanto tempo poderá usá-la. Por favor, ajude Ivan a salvar o mundo. Encontre uma rota para a cidade de Orlov, de modo que Ivan tenha que mudar os modos de marcha o menor número de vezes possível. No início do caminho, Ivan pode ligar qualquer um dos modos de marcha e você não precisa contar essa ação como uma mudança de modo de marcha.\u003c/div\u003e\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eHá dois números inteiros positivos \u003ci\u003en\u003c/i\u003e e \u003ci\u003em\u003c/i\u003e na primeira linha, o número de cidades e estradas entre elas, respectivamente \u003cnobr\u003e(2 ≤ \u003ci\u003en\u003c/i\u003e ≤ 10\u0026nbsp;000;\u003c/nobr\u003e \u003cnobr\u003e1 ≤ \u003ci\u003em\u003c/i\u003e ≤ 100\u0026nbsp;000).\u003c/nobr\u003e Nas próximas \u003ci\u003em\u003c/i\u003e linhas contêm dois números cada - números das cidades, que estão conectadas por estradas. Além disso, o primeiro é a cidade que está situada abaixo, da qual você deve subir por esta estrada. Cada estrada pode ser usada para viajar em qualquer uma das duas direções. Há no máximo uma estrada entre duas cidades. Na última linha, há os números de duas cidades, em que Ivan e o geólogo Orlov moram, respectivamente. Embora a maioria das estradas tenha sido destruída, Ivan sabe exatamente que o caminho para a cidade do geólogo Orlov existe.\u003c/div\u003e\u003c/div\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eImprima o menor número de mudanças de modos de marcha no caminho para a cidade de Orlov.\u003c/div\u003e\u003c/div\u003e"}},{"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\u003e3 2\r\n1 2\r\n3 2\r\n1 3\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003cbr\u003e\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\u003e3 3\r\n1 2\r\n2 3\r\n3 1\r\n1 3\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}