В стране Берляндии есть $n$ городов и $m$ двунаправленных дорог между ними. Все города пронумерованы от $1$ до $n$, и из любого города страны возможно добраться до любого другого. Между любой парой городов есть не более одной дороги, при этом каждая дорога имеет целую положительную длину.

Внутри страны находятся $2$ княжества, которые хотят разделить территорию между собой. Столица первого княжества находится в городе с номером $a$, а столица второго --- в городе с номером $b$.

Княжества не очень ладят между собой, поэтому также хотят, чтобы между ними обязательно была граница, состоящая из непустого множества городов, не принадлежащих ни одному из княжеств.

Определите, можно ли разделить территорию так, чтобы \textbf{одновременно} выполнялись $4$ следующих условия:
\begin{itemize}
\item если кратчайшее расстояние от некоторого города $x$ до $a$ и $b$ одинаково, то он находится на границе и не принадлежит никакому из княжеств;
\item если кратчайшее расстояние от некоторого города $x$ до $а$ меньше, чем до $b$, он принадлежит $1$-му княжеству;
\item если первые $2$ условия не верны, город $x$ принадлежит $2$-му княжеству;
\item нельзя пройти из одного княжества в другое, не пересекая граничный город;
\end{itemize}

Например, пусть $n = 7$, $m = 9$, столица первого княжества находится в городе $2$, а второго --- в городе $3$. Карта Берляндии выглядит как на рисунке ниже:

\begin{center}
  \includegraphics{graph.png} \\
\end{center}

Все города, которые будут принадлежать первому княжеству, покрашены в красный цвет, второму --- в зеленый. Города, которые будут находиться на границе, покрашены в серый.
