using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
static string InputPattern = "InputX";
static List<string> GetInputList()
{
var WillReturn = new List<string>();
if (InputPattern == "Input1") {
WillReturn.Add("11 1 4");
WillReturn.Add("1 2");
WillReturn.Add("2 3");
WillReturn.Add("3 5");
WillReturn.Add("3 6");
WillReturn.Add("2 4");
WillReturn.Add("4 7");
WillReturn.Add("1 8");
WillReturn.Add("8 9");
WillReturn.Add("8 10");
WillReturn.Add("9 11");
//1
//1
//2
//1
//3
//3
//2
//2
//3
//3
//4
}
else {
string wkStr;
while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
}
return WillReturn;
}
static int mN;
static int mS;
static int mT;
// 隣接リスト
static Dictionary<int, List<int>> mToNodeListDict = new Dictionary<int, List<int>>();
static void Main()
{
List<string> InputList = GetInputList();
int[] wkArr = { };
Action<string> SplitAct = pStr =>
wkArr = pStr.Split(' ').Select(pX => int.Parse(pX)).ToArray();
SplitAct(InputList[0]);
mN = wkArr[0];
mS = wkArr[1];
mT = wkArr[2];
foreach (string EachStr in InputList.Skip(1)) {
SplitAct(EachStr);
int FromNode = wkArr[0];
int ToNode = wkArr[1];
if (mToNodeListDict.ContainsKey(FromNode) == false) {
mToNodeListDict[FromNode] = new List<int>();
}
if (mToNodeListDict.ContainsKey(ToNode) == false) {
mToNodeListDict[ToNode] = new List<int>();
}
mToNodeListDict[FromNode].Add(ToNode);
mToNodeListDict[ToNode].Add(FromNode);
}
ExecEulerTour(mS, -1, 1);
//foreach (JyoutaiDef_EulerTour EachJyoutai in mEulerTourJyoutaiList) {
// Console.WriteLine("CurrNode={0},Level={1}", EachJyoutai.CurrNode, EachJyoutai.Level);
//}
// 最初に登場するInd[ノード]なDict
var FirstApperIndDict = new Dictionary<int, int>();
// Level[ノード]なDict
var LevelDict = new Dictionary<int, int>();
// スパーステーブルのコンストラクタに使うLevelのList
var LevelList = new List<int>();
for (int I = 0; I <= mEulerTourJyoutaiList.Count - 1; I++) {
int CurrNode = mEulerTourJyoutaiList[I].CurrNode;
if (FirstApperIndDict.ContainsKey(CurrNode) == false) {
FirstApperIndDict[CurrNode] = I;
}
LevelDict[CurrNode] = mEulerTourJyoutaiList[I].Level;
LevelList.Add(mEulerTourJyoutaiList[I].Level);
}
var InsSparseTable = new SparseTable<int>(LevelList, true);
var sb = new System.Text.StringBuilder();
for (int I = 1; I <= mN; I++) {
int Ind1 = FirstApperIndDict[I];
int Ind2 = FirstApperIndDict[mT];
int LeftInd = Math.Min(Ind1, Ind2);
int RightInd = Math.Max(Ind1, Ind2);
int LCALevel = InsSparseTable.Query(LeftInd, RightInd);
int Answer = Math.Abs(LCALevel - LevelDict[I]);
sb.Append(Answer + 1);
sb.AppendLine();
}
Console.Write(sb.ToString());
}
struct JyoutaiDef_EulerTour
{
internal int CurrNode;
internal int Level;
}
// DFSを行い、下記の2通りのタイミングでノードをAddする
// 1 最初の訪問時
// 2 子の部分木を訪問時
static List<JyoutaiDef_EulerTour> mEulerTourJyoutaiList = new List<JyoutaiDef_EulerTour>();
static void ExecEulerTour(int pCurrNode, int pParentNode, int pLevel)
{
JyoutaiDef_EulerTour WillAdd;
WillAdd.CurrNode = pCurrNode;
WillAdd.Level = pLevel;
mEulerTourJyoutaiList.Add(WillAdd);
if (mToNodeListDict.ContainsKey(pCurrNode)) {
foreach (int EachToNode in mToNodeListDict[pCurrNode]) {
if (EachToNode == pParentNode) continue;
ExecEulerTour(EachToNode, pCurrNode, pLevel + 1);
mEulerTourJyoutaiList.Add(WillAdd);
}
}
}
}
#region SparseTable
// スパーステーブル
internal class SparseTable<Type>
{
private Type[] mInitArr;
private long UB_0;
private long UB_1;
// 最小値か最大値[開始Ind,2の指数]なArr
private Type[,] mMinOrMaxArr;
// Log2の値[2べきな値] なDict
private Dictionary<long, long> mLogDict = new Dictionary<long, long>();
// 最小値を取得するか？
private bool mIsMin = false;
// コンストラクタ
internal SparseTable(IEnumerable<Type> pInitEnum, bool pIsMin)
{
mIsMin = pIsMin;
mInitArr = pInitEnum.ToArray();
UB_0 = mInitArr.GetUpperBound(0);
long Sisuu = 0;
long Beki2 = 1;
while (true) {
mLogDict[Beki2] = Sisuu;
if (Beki2 > mInitArr.Length) {
break;
}
Beki2 *= 2;
Sisuu++;
}
UB_1 = Sisuu;
mMinOrMaxArr = new Type[UB_0 + 1, UB_1 + 1];
// 長さ1の分を初期化
for (long I = 0; I <= UB_0; I++) {
mMinOrMaxArr[I, 0] = mInitArr[I];
}
for (long LoopLength = 2; LoopLength < long.MaxValue; LoopLength *= 2) {
bool WillBreak = true;
long HalfRange = LoopLength / 2;
for (long I = 0; I <= UB_0; I++) {
long StaInd1 = I;
long EndInd1 = I + HalfRange - 1;
long StaInd2 = EndInd1 + 1;
long EndInd2 = StaInd2 + HalfRange - 1;
if (EndInd2 > UB_0) break;
var KouhoList = new List<Type>();
KouhoList.Add(mMinOrMaxArr[I, mLogDict[HalfRange]]);
KouhoList.Add(mMinOrMaxArr[StaInd2, mLogDict[HalfRange]]);
if (mIsMin) {
mMinOrMaxArr[I, mLogDict[LoopLength]] = KouhoList.Min();
}
else {
mMinOrMaxArr[I, mLogDict[LoopLength]] = KouhoList.Max();
}
WillBreak = false;
}
if (WillBreak) break;
}
}
// 閉区間 [L,R]の最小値または最大値を求める
internal Type Query(long pL, long pR)
{
// 区間を内包する2べきを返す
long Beki2 = 1;
long Sisuu = 0;
while (true) {
long LeftRangeMax = pL + Beki2 - 1;
long RightRangeMin = pR - Beki2 + 1;
if (LeftRangeMax + 1 >= RightRangeMin) {
break;
}
Beki2 *= 2;
Sisuu++;
}
var KouhoList = new List<Type>();
KouhoList.Add(mMinOrMaxArr[pL, Sisuu]);
KouhoList.Add(mMinOrMaxArr[pR - Beki2 + 1, Sisuu]);
if (mIsMin) {
return KouhoList.Min();
}
return KouhoList.Max();
}
}
#endregion